제출 #1258088

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258088		mquang	Potemkin cycle (CEOI15_indcyc)	C++20	100 / 100	174 ms	2980 KiB

indcyc

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
const int INF = 1e18, N = 1e3 + 5, MOD = 1e9 + 7;
vector<int> g[N];
bool chk[N][N], vis[N];
int dist[N], par[N], qu[N], cnt;
void dfs(int u, int p){
	if (u == p || vis[u]) return;
	vis[u] = true;
	if(chk[u][p]){
		qu[cnt++] = u;
		return;
	}
	for(int v : g[u]) dfs(v, p);
}
int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
    int n, m; 
    cin >> n >> m;
	while(m--){
		int u, v;
        cin >> u >> v;
        u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
		chk[u][v] = chk[v][u] = true;
	}
	for(int i = 0; i < n; i++){
		for(int i1 = 0; i1 < n; i1++) vis[i1] = false;
		vis[i] = true;
		for(int i1 = 0; i1 < n; i1++)
			if(!chk[i1][i] && !vis[i1]){
				cnt = 0, dfs(i1, i);
				for(int z = 0; z < cnt; z++){
					int s = qu[z];
					for(int h = z + 1; h < cnt; h++){
						int t = qu[h];
						if(!chk[s][t]){
							for(int i2 = 0; i2 < n; i2++) dist[i2] = n;
							int cnt = 0; 
                            dist[s] = 0; 
                            par[s] = -1; 
                            qu[cnt++] = s;
							for(int h = 0; h < cnt; h++){
								int u = qu[h], d = dist[i1] + 1;
								for(int v : g[u]){
									if(v != i && (v == t || !chk[v][i]) && dist[v] == n){
										dist[v] = d; 
                                        par[v] = u;
                                        qu[cnt++] = v;
                                    }
                                }
							}
							cout << s + 1 << ' ' << i + 1;
							for(int i2 = t; i2 != s; i2 = par[i2]) cout << ' ' << i2 + 1;
							return 0;
						}
					}
				}
			}
	}
	cout << "no";
    cerr << "Time: " << TIME;
    return 0;
}

• 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: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10