oj.uz

Submission #54776

# Submission time Handle Problem Language Result Execution time Memory
54776 2018-07-05T05:03:16 Z 2등은 나의 것^^(#2060) Potemkin cycle (CEOI15_indcyc) C++11
20 / 100
 26 ms 3064 KB 
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>edge[1212];
bool is_gone_dfs1[1212];
int depth[1212], MX[1212], ck[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] > dep)continue;
			if (MX[w] < depth[next])MX[w] = depth[next];
			continue;
		}
		dfs1(next, dep + 1, w);
	}
}
int stdep;
int dfs2(int w) {
	if (ck[w]) { printf("%d ", w); return 1; }
	for (int i = 0; i < edge[w].size(); i++) {
		int next = edge[w][i];
		if (depth[next] - depth[w] != 1)continue;
		if (MX[next] && (!ck[next] && MX[next] >= stdep))continue;
		if (dfs2(next)) { printf("%d ", w); return 1; }
	}
	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);
		edge[e].push_back(s);
	}
	for (i = 1; i <= n; i++) {
		if (is_gone_dfs1[i])continue;
		dfs1(i, 1, -1);
	}
	for (i = 1; i <= n; i++) {
		for (j = 0; j < edge[i].size(); j++) ck[edge[i][j]] = (depth[edge[i][j]] - depth[i] >= 3);
		stdep = depth[i];
		if (i == 2)
			int sp = 1;
		if (dfs2(i)) return 0;
		for (j = 0; j < edge[i].size(); j++) ck[edge[i][j]] = 0;
	}
	printf("no");
	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)':
indcyc.cpp:24: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:45:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j = 0; j < edge[i].size(); j++) ck[edge[i][j]] = (depth[edge[i][j]] - depth[i] >= 3);
               ~~^~~~~~~~~~~~~~~~
indcyc.cpp:48:8: warning: unused variable 'sp' [-Wunused-variable]
    int sp = 1;
        ^~
indcyc.cpp:50:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j = 0; j < edge[i].size(); j++) ck[edge[i][j]] = 0;
               ~~^~~~~~~~~~~~~~~~
indcyc.cpp:33: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:36: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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 3 ms 648 KB Output is correct
5 Correct 2 ms 648 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 648 KB Wrong adjacency

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 648 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 692 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 828 KB Wrong answer on graph without induced cycle
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 868 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 1732 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1732 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 3064 KB Wrong adjacency
2 Halted 0 ms 0 KB -