oj.uz

답안 #130423

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130423 2019-07-15T07:48:41 Z 이온조(#3149) Information (CEOI08_information) C++14
85 / 100
 547 ms 59064 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int N, M, in[2009], ou[2009], t;
vector<pii> adj[2009];
set<pii> R[2009];
bool v1[2009], v2[2009];
int h[1000009];

bool isup(int u, int v) {
	return in[u] <= in[v] && ou[u] >= ou[v];
}

void dfs(int x) {
	in[x] = ++t;
	v1[x] = 1;
	for(auto& it: adj[x]) {
		if(!v1[it.first]) {
			h[it.second] = 1;
			dfs(it.first);
		}
	}
	ou[x] = t;
}

void go(int x) {
	v2[x] = 1;
	for(auto& it: adj[x]) {
		int t, i; tie(t, i) = it;
		if(!v2[t]) {
			if(h[i] == 0) {
				h[i] = 2;
				go(t);
			}
			else if(h[i] == 1 && R[t].size()) {
				int rt, ri; tie(rt, ri) = *R[t].begin();
				R[t].erase(R[t].begin());
				h[i] = 2; h[ri] = 1;
				go(t);
			}
		}
	}
}

int main() {
	scanf("%d%d",&N,&M);
	for(int i=1; i<=M; i++) {
		int u, v; scanf("%d%d",&u,&v);
		adj[u].push_back({v, i});
	}
	dfs(1);
	for(int i=1; i<=N; i++) {
		for(auto& it: adj[i]) {
			if(!h[it.second] && !isup(it.first, i)) R[it.first].insert({i, it.second});
		}
	}
	go(1);
	vector<int> A1, A2;
	for(int i=1; i<=N; i++) for(auto& it: adj[i]) {
		if(h[it.second] == 1) A1.push_back(it.second);
		if(h[it.second] == 2) A2.push_back(it.second);
	}
	if((int)A1.size() != N-1 || (int)A2.size() != N-1) puts("NONE");
	else {
		for(auto& it: A1) printf("%d ",it); puts("");
		for(auto& it: A2) printf("%d ",it);
	}
	return 0;
}

Compilation message

information.cpp: In function 'int main()':
information.cpp:66:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(auto& it: A1) printf("%d ",it); puts("");
   ^~~
information.cpp:66:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(auto& it: A1) printf("%d ",it); puts("");
                                       ^~~~
information.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&N,&M);
  ~~~~~^~~~~~~~~~~~~~
information.cpp:49:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d%d",&u,&v);
             ~~~~~^~~~~~~~~~~~~~

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 508 KB Output is correct

Subtask #5
4.0 / 4.0

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

Subtask #6
4.0 / 4.0

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

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

Subtask #8
4.0 / 4.0

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

Subtask #9
4.0 / 4.0

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

Subtask #10
4.0 / 4.0

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

Subtask #11
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 632 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 504 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 46 ms 6264 KB Output is correct

Subtask #16
4.0 / 4.0

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

Subtask #17
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 4180 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 760 KB Output is correct

Subtask #20
4.0 / 4.0

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

Subtask #21
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 547 ms 59064 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #22
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 341 ms 34424 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #23
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 358 ms 35960 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #24
5.0 / 5.0

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