oj.uz

Submission #54793

# Submission time Handle Problem Language Result Execution time Memory
54793 2018-07-05T05:46:47 Z 2등은 나의 것^^(#2060) Potemkin cycle (CEOI15_indcyc) C++11
20 / 100
 1000 ms 15452 KB 
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
vector<int>edge[1212];
int depth[1212], is_gone_dfs1[1212];
set<pair<int, int>>L[1212];  set<int>M[1212];
void dfs1(int w,int dep,int bef) {
	depth[w] = dep; is_gone_dfs1[w] = 1;
	for (int i = 0; i < edge[w].size(); i++) {
		int next = edge[w][i];
		if (is_gone_dfs1[next]) {
			if(next==bef || depth[next] > depth[w])continue;
			L[w].insert({ depth[next],next });
			continue;
		}
		dfs1(next, dep + 1, w);
	}
}
int stdep, D[1212], st, go[1212], cck;
int dfs2(int w, int bef) {
	set<pair<int, int>>::iterator it = L[w].lower_bound({stdep + 1,-1e9});
	if (bef != -1 && it == L[w].end())D[w] = D[bef] + 1, go[w] = bef;
	if (bef != -1 && it != L[w].end())D[w] = D[it->second] + 1, go[w] = it->second;
	if (D[w] >= 4 && M[w].find(st) != M[w].end())return w;
	if (D[w] == 3 && M[w].find(st) != M[w].end())cck = 1;
	if (M[w].find(st) != M[w].end())D[w] = 2, go[w] = st;
	for (int i = 0; i < edge[w].size(); i++) {
		int next = edge[w][i];
		if (depth[next] - depth[w] != 1)continue;
		int k = dfs2(next, w);
		if (k) return k;
	}
	return 0;
}
int main() {
	int n, m; scanf("%d%d", &n, &m);
	int i, j;
	for (i = 0; i < m; i++) {
		int s, e; scanf("%d%d", &s, &e);
		edge[s].push_back(e); M[s].insert(e);
		edge[e].push_back(s); M[e].insert(s);
	}
	for (i = 1; i <= n; i++) {
		if (is_gone_dfs1[i])continue;
		dfs1(i, 1, -1);
	}
	for (i = 1; i <= n; i++) {
		D[i] = 1; st = i; stdep = depth[i];
		int now = dfs2(i, -1);
		if (now) {
			while (now != i) {
				printf("%d ", now);
				now = go[now];
			}
			printf("%d ", i);
			return 0;
		}
		for (j = 1; j <= n; j++)D[j] = go[j] = 0;
	}
	printf("no");
	if (cck)while (1);
	return 0;
}

Compilation message

indcyc.cpp: In function 'void dfs1(int, int, int)':
indcyc.cpp:11:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < edge[w].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~
indcyc.cpp: In function 'int dfs2(int, int)':
indcyc.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < edge[w].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:38:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m; scanf("%d%d", &n, &m);
            ~~~~~^~~~~~~~~~~~~~~~
indcyc.cpp:41:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int s, e; scanf("%d%d", &s, &e);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Execution timed out 1083 ms 612 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 612 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 752 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 1052 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 1180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 7928 KB Output is correct
2 Correct 82 ms 7928 KB Output is correct
3 Execution timed out 1086 ms 7996 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 7996 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 15168 KB Output is correct
2 Execution timed out 1076 ms 15452 KB Time limit exceeded
3 Halted 0 ms 0 KB -