oj.uz

답안 #130392

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130392 2019-07-15T06:11:26 Z 윤교준(#3150) Information (CEOI08_information) C++14
95 / 100
 1000 ms 12536 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];
bitset<MAXM> isT1, isT2;
bitset<MAXN> isT2V, chk;

int A[MAXM], B[MAXM];

int N, M;

int findEdge(int i, int r, int ne) {
	chk[i] = true;
	for(int e : G[i]) if(e != ne && !isT2[e]) {
		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];
				if(isT2V[v] || isT1[e]) continue;
				isT2[e] = true;
				isT2V[v] = true;
				PQ.push(v);
			}
		}
		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;
			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];
		G[A[i]].eb(i);
	}

	makeT1();
	makeT2();

	prtAns();
	return 0;
}

Compilation message

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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct

Subtask #6
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct

Subtask #7
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 508 KB Output is correct

Subtask #8
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 476 KB Output is correct

Subtask #9
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct

Subtask #10
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct

Subtask #11
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct

Subtask #12
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #13
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct

Subtask #14
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct

Subtask #15
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 1784 KB Output is correct

Subtask #16
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 3176 KB Output is correct

Subtask #17
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 1784 KB Output is correct

Subtask #18
4.0 / 4.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 632 KB Output is correct

Subtask #20
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 632 KB Output is correct

Subtask #21
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 208 ms 12476 KB Output is correct

Subtask #22
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 200 ms 12124 KB Output is correct

Subtask #23
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1031 ms 12536 KB Time limit exceeded

Subtask #24
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 632 KB Output is correct
2 Correct 3 ms 504 KB Output is correct