oj.uz

Submission #460992

# Submission time Handle Problem Language Result Execution time Memory
460992 2021-08-09T11:46:20 Z kingfran1907 Potemkin cycle (CEOI15_indcyc) C++14
70 / 100
 1000 ms 5500 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 p = 1; p <= n; p++) dis[p] = 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 node = q.front();
					q.pop();
					
					for (int tren : graph[node]) {
						if (dis[tren] == inf) {
							dis[tren] = 1 + dis[node];
							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);
				reverse(v.begin(), v.end());
				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:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 324 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 9 ms 752 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 1540 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct
3 Correct 3 ms 1612 KB Output is correct
4 Correct 111 ms 1612 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1484 KB Output is correct
2 Correct 128 ms 1560 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 4812 KB Output is correct
2 Correct 78 ms 4684 KB Output is correct
3 Execution timed out 1091 ms 5104 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4556 KB Output is correct
2 Execution timed out 1079 ms 4596 KB Time limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3072 KB Output is correct
2 Correct 126 ms 3760 KB Output is correct
3 Correct 199 ms 5500 KB Output is correct
4 Execution timed out 1063 ms 5452 KB Time limit exceeded