Submission #2707880
Source Code Expand
#include <algorithm> #include <cassert> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <ctime> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <list> #include <map> #include <queue> #include <random> #include <set> #include <sstream> #include <string> #include <utility> #include <vector> #define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++) #define DEBUGP(val) cerr << #val << "=" << val << "\n" using namespace std; typedef long long int ll; typedef vector<int> VI; typedef vector<ll> VL; typedef pair<int, int> PI; const int N = 100100; VI g[N]; bool vis[N]; int col[N]; bool is_bipartite(int v, int c) { if (vis[v]) { return c == col[v]; } vis[v] = true; col[v] = c; for (int w: g[v]) { if (not is_bipartite(w, 1 - c)) { return false; } } return true; } int main(void) { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; REP(i, 0, n) { int a, b; cin >> a >> b; a--, b--; g[a].push_back(b); g[b].push_back(a); } int mi = n + 1; int mincut, maxcut = -1; REP(i, 0, n) { mi = min(mi, (int) g[i].size()); } mincut = mi; maxcut = n - (is_bipartite(0, 0) ? 0 : 1); cout << mincut << " " << maxcut << endl; }
Submission Info
Submission Time | |
---|---|
Task | C - 最小カットと最大カット |
User | kobae964 |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1274 Byte |
Status | AC |
Exec Time | 40 ms |
Memory | 9344 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 | 2 ms | 2560 KB |
scrambled_01.txt | AC | 2 ms | 2560 KB |
scrambled_02.txt | AC | 2 ms | 2560 KB |
scrambled_03.txt | AC | 40 ms | 9344 KB |
scrambled_04.txt | AC | 40 ms | 9344 KB |
scrambled_05.txt | AC | 24 ms | 6784 KB |
scrambled_06.txt | AC | 16 ms | 5248 KB |
scrambled_07.txt | AC | 37 ms | 8832 KB |
scrambled_08.txt | AC | 13 ms | 4736 KB |
scrambled_09.txt | AC | 17 ms | 5376 KB |
scrambled_10.txt | AC | 26 ms | 6648 KB |
scrambled_11.txt | AC | 11 ms | 4092 KB |
scrambled_12.txt | AC | 21 ms | 5880 KB |
scrambled_13.txt | AC | 20 ms | 5624 KB |
scrambled_14.txt | AC | 37 ms | 6272 KB |
scrambled_15.txt | AC | 26 ms | 5120 KB |
scrambled_16.txt | AC | 14 ms | 3968 KB |
scrambled_17.txt | AC | 14 ms | 3968 KB |
scrambled_18.txt | AC | 38 ms | 6272 KB |
scrambled_19.txt | AC | 4 ms | 2944 KB |
scrambled_20.txt | AC | 23 ms | 4992 KB |
scrambled_21.txt | AC | 13 ms | 3968 KB |
scrambled_22.txt | AC | 24 ms | 5248 KB |
scrambled_23.txt | AC | 21 ms | 4224 KB |
scrambled_24.txt | AC | 15 ms | 4096 KB |
scrambled_25.txt | AC | 18 ms | 4480 KB |
scrambled_26.txt | AC | 15 ms | 4096 KB |
scrambled_27.txt | AC | 23 ms | 4864 KB |
scrambled_28.txt | AC | 20 ms | 4736 KB |