oj.uz

Submission #460986

# Submission time Handle Problem Language Result Execution time Memory
460986 2021-08-09T11:42:20 Z kingfran1907 Potemkin cycle (CEOI15_indcyc) C++14
0 / 100
 390 ms 5184 KB 
#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 1010;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 18;
const int off = 1 << logo;
const int treesiz = off << 1;

int n, m;
vector< int > graph[maxn];
int eg[maxn][maxn];
int dis[maxn];
queue< int > q;

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		
		graph[a].push_back(b);
		graph[b].push_back(a);
		eg[a][b] = eg[b][a] = 1;
	}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < graph[i].size(); j++) {
			for (int k = j + 1; k < graph[i].size(); k++) {
				int x = graph[i][j];
				int y = graph[i][k];
				if (eg[x][y]) continue;
				
				for (int i = 1; i <= n; i++) dis[i] = inf;
				dis[i] = -1;
				for (int tren : graph[i]) dis[tren] = -1;
				dis[y] = inf; dis[x] = 0;
				
				q.push(x);
				while (!q.empty()) {
					int x = q.front();
					q.pop();
					
					for (int tren : graph[x]) {
						if (dis[tren] == inf) {
							dis[tren] = 1 + dis[x];
							q.push(tren);
						}
					}
				}
				if (dis[y] == inf) continue;
				
				vector< int > v;
				int ptr = y;
				while (ptr != x) {
					v.push_back(ptr);
					for (int tren : graph[ptr]) {
						if (dis[tren] + 1 == dis[ptr]) {
							ptr = tren;
							break;
						}
					}
				}
				
				printf("%d %d ", i, x);
				for (int i = 0; i < v.size(); i++) 
					printf("%d ", v[i]);
				printf("\n");
				return 0;
			}
		}
	}
	printf("no\n");
	return 0;
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:34:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for (int j = 0; j < graph[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~
indcyc.cpp:35:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |    for (int k = j + 1; k < graph[i].size(); k++) {
      |                        ~~^~~~~~~~~~~~~~~~~
indcyc.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
indcyc.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
indcyc.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 1568 KB Output is correct
2 Incorrect 3 ms 1484 KB Wrong adjacency
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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