# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
598984 |
2022-07-19T08:38:45 Z |
이동현(#8460) |
Potemkin cycle (CEOI15_indcyc) |
C++17 |
|
1000 ms |
31232 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
int n, m;
vector<int> way[1004];
int chk[1004], ss, from[1004], did[1004], didN;
int que[1004], f, r;
void bfs(int s, int e){
f = r = 0;
que[r++] = s;
did[s] = didN;
while(f < r){
int now = que[f]; ++f;
for(auto&nxt:way[now]){
if((nxt != e && !chk[nxt]) || did[nxt] == didN) continue;
from[nxt] = now;
que[r++] = nxt;
did[nxt] = didN;
}
}
if(did[e] == didN){
int now = e;
while(true){
cout << now << ' ';
if(now == s) break;
now = from[now];
}
cout << ss << '\n';
exit(0);
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
map<pair<int, int>, int> cant;
for(int i = 1; i <= m; ++i){
int x, y; cin >> x >> y;
if(x > y) swap(x, y);
way[x].push_back(y);
way[y].push_back(x);
cant[{x, y}] = 1;
}
for(int i = 1; i <= n; ++i) chk[i] = 1;
for(int i = 1; i <= n; ++i){
chk[i] = 0;
sort(way[i].begin(), way[i].end());
for(auto&nxt:way[i]){
chk[nxt] = 0;
}
ss = i;
for(int j = 0; j < (int)way[i].size(); ++j){
for(int k = j + 1; k < (int)way[i].size(); ++k){
if(cant[{way[i][j], way[i][k]}]) continue;
++didN;
bfs(way[i][j], way[i][k]);
}
}
chk[i] = 1;
for(auto&nxt:way[i]){
chk[nxt] = 1;
}
}
cout << "no\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
7 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
95 ms |
756 KB |
Output is correct |
2 |
Correct |
2 ms |
612 KB |
Output is correct |
3 |
Correct |
4 ms |
736 KB |
Output is correct |
4 |
Correct |
85 ms |
1764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
596 KB |
Output is correct |
2 |
Correct |
84 ms |
3192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
457 ms |
4312 KB |
Output is correct |
2 |
Correct |
65 ms |
1984 KB |
Output is correct |
3 |
Execution timed out |
1092 ms |
4952 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
70 ms |
2136 KB |
Output is correct |
2 |
Execution timed out |
1091 ms |
31232 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
347 ms |
7328 KB |
Output is correct |
2 |
Execution timed out |
1081 ms |
7216 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |