# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
130394 | 2019-07-15T06:18:39 Z | 윤교준(#3150) | Information (CEOI08_information) | C++14 | 672 ms | 16772 KB |
#include <bits/stdc++.h> #define eb emplace_back #define sz(V) ((int)(V).size()) #define allv(V) ((V).begin()),((V).end()) #define sorv(V) sort(allv(V)) #define univ(V) (V).erase(unique(allv(V)),(V).end()) #define upmin(a,b) (a)=min((a),(b)) #define INF (0x3f3f3f3f) #define INFLL (0x3f3f3f3f3f3f3f3fll) using namespace std; typedef long long ll; typedef pair<int, int> pii; inline void fuk() { puts("NONE"); exit(0); } const int MX = 75000000; const int MAXN = 2005; const int MAXM = 1000005; queue<int> PQ; vector<int> G[MAXN], T[MAXN]; bitset<MAXM> isT1, isT2; bitset<MAXN> isT2V, chk; int A[MAXM], B[MAXM]; int cnt = 0; int N, M; int findEdge(int i, int r, int ne) { if(MX < cnt) fuk(); chk[i] = true; for(int e : G[i]) if(e != ne && !isT2[e]) { cnt++; int v = B[e]; if(chk[v]) continue; if(r == v) return e; if(!isT1[e]) continue; int ret = findEdge(v, r, ne); if(ret) return ret; } return 0; } void makeT2() { isT2V[1] = true; PQ.push(1); for(;;) { for(int idx; !PQ.empty();) { idx = PQ.front(); PQ.pop(); for(int e : G[idx]) { int v = B[e]; cnt++; if(MX < cnt) fuk(); if(isT2V[v] || isT1[e]) continue; isT2[e] = true; isT2V[v] = true; PQ.push(v); } cnt++; } if(isT2V.count() == N) break; for(int e = 1, a, b; e <= M; e++) if(isT1[e]) { a = A[e]; b = B[e]; if(!isT2V[a] || isT2V[b]) continue; cnt++; if(MX < cnt) fuk(); chk.reset(); int ret = findEdge(1, b, e); if(!ret) continue; isT1[e] = false; isT2[e] = true; isT1[ret] = true; isT2V[b] = true; PQ.push(b); break; } if(PQ.empty()) fuk(); } } void dfsT1(int i) { chk[i] = true; for(int e : G[i]) { int v = B[e]; if(chk[v]) continue; isT1[e] = true; dfsT1(v); } } void makeT1() { dfsT1(1); for(int i = 2; i <= N; i++) if(!chk[i]) fuk(); chk.reset(); for(int i = 1; i <= M; i++) if(isT1[i]) T[A[i]].eb(i); } void prtAns() { vector<int> V1, V2; for(int i = 1; i <= M; i++) { if(isT1[i] && isT2[i]) fuk(); if(isT1[i]) V1.eb(i); if(isT2[i]) V2.eb(i); } if(sz(V1) != N-1 || sz(V2) != N-1) fuk(); for(int v : V1) printf("%d ", v); puts(""); for(int v : V2) printf("%d ", v); puts(""); } int main() { ios::sync_with_stdio(false); cin >> N >> M; for(int i = 1; i <= M; i++) cin >> A[i] >> B[i]; { vector<int> O; for(int i = 1; i <= M; i++) O.eb(i); shuffle(allv(O), mt19937(time(0))); for(int e : O) G[A[e]].eb(e); } makeT1(); makeT2(); prtAns(); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 508 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 636 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 2164 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 263 ms | 3788 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 141 ms | 2288 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 632 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 632 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 334 ms | 16640 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 582 ms | 16036 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 672 ms | 16772 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 632 KB | Output is correct |
2 | Correct | 3 ms | 508 KB | Output is correct |