oj.uz

Submission #130393

# Submission time Handle Problem Language Result Execution time Memory
130393 2019-07-15T06:17:13 Z 윤교준(#3150) Information (CEOI08_information) C++14
95 / 100
 438 ms 16736 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 = 30000000;
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

information.cpp: In function 'void makeT2()':
information.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(isT2V.count() == N) break;
      ~~~~~~~~~~~~~~^~~~
information.cpp: In function 'void prtAns()':
information.cpp:110:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int v : V1) printf("%d ", v); puts("");
  ^~~
information.cpp:110: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:111:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int v : V2) printf("%d ", v); puts("");
  ^~~
information.cpp:111: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 504 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 376 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 4 ms 632 KB Output is correct

Subtask #11
4.0 / 4.0

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

Subtask #12
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 #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 28 ms 2284 KB Output is correct

Subtask #16
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 3936 KB Output is correct

Subtask #17
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 2164 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 5 ms 632 KB Output is correct

Subtask #20
4.0 / 4.0

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

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 16604 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 15992 KB Output is correct

Subtask #23
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 438 ms 16736 KB Output isn't correct

Subtask #24
5.0 / 5.0

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