Submission #460992

#	Time	Username	Problem	Language	Result	Execution time	Memory
460992		kingfran1907	Potemkin cycle (CEOI15_indcyc)	C++14	70 / 100	1091 ms	5500 KiB

indcyc

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10