Submission #25157

#	Time	Username	Problem	Language	Result	Execution time	Memory
25157		kajebiii	Potemkin cycle (CEOI15_indcyc)	C++14	50 / 100	1000 ms	10960 KiB

indcyc

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 1e3 + 10;

int N, M, D[MAX_N][MAX_N];
vector<int> Ed[MAX_N];

int ChkV[MAX_N], UNF[MAX_N], Val[MAX_N];
int F(int v) {return UNF[v]==v?v:UNF[v]=F(UNF[v]);}
void U(int a, int b) {
	a = F(a); b = F(b);
	if(rand()%2) UNF[a] = b; else UNF[b] = a;
}
int P[MAX_N];
void findPath(int r, int x, int y) {
	vector<bool> vis(N+1, false);
//	printf("%d %d %d\n", r, x, y);

	queue<int> Q; Q.push(x); vis[x] = true; vis[r] = true;
	while(!Q.empty()) {
		int v = Q.front(); Q.pop();
		for(int w : Ed[v]) {
			if(vis[w]) continue;
			if(w == y) {
				Q.push(w); P[w] = v;
				break;
			} else {
				if(ChkV[w] == r) continue;
				vis[w] = true;
				Q.push(w); P[w] = v;
			}
		}
	}

	int now = y;
	while(true) {
		printf("%d ", now);
		if(now == x) break;
		now = P[now];
	}
	printf("%d\n", r);
}

int Vis[MAX_N][MAX_N];
int main() {
	cin >> N >> M;
	while(M--) {
		int x, y;
		scanf("%d%d", &x, &y);
		Ed[x].push_back(y); Ed[y].push_back(x);
		D[x][y] = D[y][x] = 1;
	}

	for(int v=1; v<=N; v++) {
		for(int i=1; i<=N; i++) UNF[i] = i;

		for(int w : Ed[v]) ChkV[w] = v; ChkV[v] = v;
		for(int x=1; x<=N; x++) if(ChkV[x] != v) 
			for(int y : Ed[x]) if(ChkV[y] != v)
				U(x, y);

		vector<int> Gp[MAX_N];
		for(int i=1; i<=N; i++) if(ChkV[i] != v)
			for(int x : Ed[i]) if(ChkV[x] == v && x != v && Vis[F(i)][x] != v) {
				Gp[F(i)].push_back(x);
				Vis[F(i)][x] = v;
			}
		
		for(int i=1; i<=N; i++) 
			if(SZ(Gp[i]) >= 2) {
//				for(int x : Gp[i]) printf("%d ", x); puts("");
				for(int x=0; x<SZ(Gp[i]); x++) for(int y=x+1; y<SZ(Gp[i]); y++) {
					int &a = Gp[i][x], &b = Gp[i][y];
					if(D[a][b] == 0) {
						findPath(v, a, b);
						return 0;
					}
				}
			}
	}
	puts("no");
	return 0;
}

Compilation message (stderr)

indcyc.cpp: In function 'int main()':
indcyc.cpp:62:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
                        ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10