# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
46860 | HachikujiMayoi | Potemkin cycle (CEOI15_indcyc) | C++14 | 192 ms | 6880 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 1007;
int n, m;
int blocked[N], par[N], vis[N];
vector <int> g[N], comp[N];
int G[N][N];
int Get(int a){
if(par[a] == a) return a;
return par[a] = Get(par[a]);
}
void Union(int a, int b){
a = Get(a);
b = Get(b);
if(a == b) return;
if(comp[b].size() > comp[a].size()) swap(a, b);
par[b] = a;
for(auto i : comp[b]) comp[a].push_back(i);
}
void dfs(int at){
vis[at] = 1;
if(blocked[at]) return;
for(auto i : g[at]){
if(!vis[i]){
Union(at, i);
dfs(i);
}
}
}
void solve(int a, int b, int c){
blocked[a] = 0;
blocked[c] = 0;
vector <int> dis(n + 1, N), dad(n + 1, 0);
queue <int> q;
dis[a] = 0;
q.push(a);
while(!q.empty()){
int u = q.front();
q.pop();
for(auto i : g[u]){
if(blocked[i]) continue;
if(dis[i] > dis[u] + 1){
dis[i] = dis[u] + 1;
dad[i] = u;
q.push(i);
}
}
}
printf("%d %d %d", a, b, c);
int cur = dad[c];
while(cur != a){
printf(" %d", cur);
cur = dad[cur];
}
printf("\n");
}
int main(){
int x, y;
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; ++i){
scanf("%d %d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
G[x][y] = 1;
G[y][x] = 1;
}
for(int i = 1; i <= n; ++i) G[i][i] = 1;
for(int i = 1; i <= n; ++i){
memset(blocked, 0, sizeof(blocked));
memset(vis, 0, sizeof(vis));
blocked[i] = 1;
for(auto j : g[i]){
blocked[j] = 1;
}
for(int j = 1; j <= n; ++j){
if(blocked[j]) comp[j] = {j};
else comp[j] = {};
par[j] = j;
}
for(int j = 1; j <= n; ++j){
if(!vis[j]) dfs(j);
}
for(int j : g[i]){
int k = Get(j);
for(auto o : comp[k]){
if(!G[j][o]){
solve(j, i, o);
return 0;
}
}
}
}
printf("no\n");
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |