Submission #371621
Source Code Expand
#include <cstring> #include <algorithm> #include <vector> #include <map> #include <queue> #include <set> #include <cassert> #include <cstdio> #include <iostream> #include <unordered_map> using namespace std; typedef long long ll; typedef unsigned long long ull; const int MN = 110000; int n; int l[MN], r[MN]; int deg[MN]; vector<int> g[MN]; bool visit[MN]; int color[MN]; void dfs(int p, int c) { if (visit[p]) return; visit[p] = true; color[p] = c; for (int d: g[p]) { dfs(d, 1-c); } } int main() { cin >> n; assert(n >= 3); for (int i = 0; i < n; i++) { int a, b; cin >> a >> b; a--; b--; l[i] = a; r[i] = b; g[a].push_back(b); g[b].push_back(a); deg[a]++; deg[b]++; } int mi = 100000; for (int i = 0; i < n; i++) { mi = min(mi, deg[i]); } assert(mi <= 2); dfs(0, 0); int ma = 0; for (int i = 0; i < n; i++) { assert(visit[i]); if (color[l[i]] != color[r[i]]) { ma++; } } assert(ma >= n-1); printf("%d %d\n", mi, ma); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 最小カットと最大カット |
User | yosupo |
Language | C++11 (GCC 4.9.2) |
Score | 100 |
Code Size | 1190 Byte |
Status | AC |
Exec Time | 178 ms |
Memory | 11300 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | scrambled_00.txt, scrambled_01.txt, scrambled_02.txt, scrambled_03.txt, scrambled_04.txt, scrambled_05.txt, scrambled_06.txt, scrambled_07.txt, scrambled_08.txt, scrambled_09.txt, scrambled_10.txt, scrambled_11.txt, scrambled_12.txt, scrambled_13.txt, scrambled_14.txt, scrambled_15.txt, scrambled_16.txt, scrambled_17.txt, scrambled_18.txt, scrambled_19.txt, scrambled_20.txt, scrambled_21.txt, scrambled_22.txt, scrambled_23.txt, scrambled_24.txt, scrambled_25.txt, scrambled_26.txt, scrambled_27.txt, scrambled_28.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
scrambled_00.txt | AC | 30 ms | 3352 KB |
scrambled_01.txt | AC | 31 ms | 3296 KB |
scrambled_02.txt | AC | 28 ms | 3484 KB |
scrambled_03.txt | AC | 175 ms | 11300 KB |
scrambled_04.txt | AC | 178 ms | 11300 KB |
scrambled_05.txt | AC | 119 ms | 8228 KB |
scrambled_06.txt | AC | 85 ms | 6364 KB |
scrambled_07.txt | AC | 166 ms | 10588 KB |
scrambled_08.txt | AC | 70 ms | 5796 KB |
scrambled_09.txt | AC | 86 ms | 6556 KB |
scrambled_10.txt | AC | 153 ms | 8472 KB |
scrambled_11.txt | AC | 76 ms | 5280 KB |
scrambled_12.txt | AC | 127 ms | 7452 KB |
scrambled_13.txt | AC | 125 ms | 7200 KB |
scrambled_14.txt | AC | 168 ms | 8104 KB |
scrambled_15.txt | AC | 130 ms | 6696 KB |
scrambled_16.txt | AC | 76 ms | 5156 KB |
scrambled_17.txt | AC | 76 ms | 5160 KB |
scrambled_18.txt | AC | 167 ms | 8224 KB |
scrambled_19.txt | AC | 38 ms | 3744 KB |
scrambled_20.txt | AC | 114 ms | 6432 KB |
scrambled_21.txt | AC | 77 ms | 5152 KB |
scrambled_22.txt | AC | 125 ms | 6692 KB |
scrambled_23.txt | AC | 85 ms | 5412 KB |
scrambled_24.txt | AC | 80 ms | 5288 KB |
scrambled_25.txt | AC | 96 ms | 5792 KB |
scrambled_26.txt | AC | 83 ms | 5280 KB |
scrambled_27.txt | AC | 112 ms | 6308 KB |
scrambled_28.txt | AC | 105 ms | 6056 KB |