oj.uz

Submission #130396

# Submission time Handle Problem Language Result Execution time Memory
130396 2019-07-15T06:31:44 Z 윤교준(#3150) Information (CEOI08_information) C++14
95 / 100
 1000 ms 12640 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 MAXN = 2005;
const int MAXM = 1000005;

queue<int> PQ;

vector<int> G[MAXN], T[MAXN];
unordered_set<int> T1E;
bitset<MAXM> isT1, isT2;
bitset<MAXN> isT2V, chk;

int A[MAXM], B[MAXM];

int N, M;

bool cmp(int a, int b) { return B[a] < B[b]; }

int findEdge(int i, int r, int ne) {
	chk[i] = true;
	B[M+1] = r;
	int es = int(lower_bound(allv(G[i]), M+1, cmp) - G[i].begin());
	for(int ei = es, dg = sz(G[i]), e; ei < dg; ei++) {
		e = G[i][ei];
		if(B[e] != r) break;
		if(e != ne && !isT2[e]) return e;
	}
	for(int e : G[i]) if(e != ne && isT1[e]) {
		int v = B[e];
		if(chk[v]) 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];
				if(isT2V[v] || isT1[e]) continue;
				isT2[e] = true;
				isT2V[v] = true;
				PQ.push(v);
			}
		}
		if(isT2V.count() == N) break;

		for(int e : T1E) {
			int a = A[e], b = B[e];
			if(!isT2V[a] || isT2V[b]) continue;
			chk.reset();
			int ret = findEdge(1, b, e);
			if(!ret) continue;

			T1E.erase(e);
			isT1[e] = false; isT2[e] = true;

			T1E.insert(ret);
			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);
		T1E.insert(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];
		G[A[i]].eb(i);
	}
	for(int i = 1; i <= N; i++) sort(allv(G[i]), cmp);

	makeT1();
	makeT2();

	prtAns();
	return 0;
}

Compilation message

information.cpp: In function 'void makeT2()':
information.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(isT2V.count() == N) break;
      ~~~~~~~~~~~~~~^~~~
information.cpp: In function 'void prtAns()':
information.cpp:116:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int v : V1) printf("%d ", v); puts("");
  ^~~
information.cpp:116:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(int v : V1) printf("%d ", v); puts("");
                                    ^~~~
information.cpp:117:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int v : V2) printf("%d ", v); puts("");
  ^~~
information.cpp:117:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(int v : V2) printf("%d ", v); puts("");
                                    ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct

Subtask #7
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct

Subtask #9
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct

Subtask #10
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 632 KB Output is correct

Subtask #11
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct

Subtask #12
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 548 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #13
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct

Subtask #14
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct

Subtask #15
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1784 KB Output is correct

Subtask #16
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 3004 KB Output is correct

Subtask #17
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1912 KB Output is correct

Subtask #18
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct

Subtask #19
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 760 KB Output is correct

Subtask #20
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 12640 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 12076 KB Output is correct

Subtask #23
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 12544 KB Time limit exceeded

Subtask #24
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 760 KB Output is correct
2 Correct 3 ms 504 KB Output is correct