# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
365989 | 2021-02-12T16:18:56 Z | kostia244 | Potemkin cycle (CEOI15_indcyc) | C++17 | 844 ms | 6516 KB |
#include<bits/stdc++.h> #define all(x) begin(x), end(x) using namespace std; using ll = long long; const int maxn = 1002, maxm = 2e5 + 3; int can[maxm][maxn], hv[maxn][maxn], vis[maxm], n, m; vector<array<int, 2>> edges; vector<int> cur; void reduce() { int r = 0; while(r < cur.size()) { int ok = 1; for(int i = 1; i+1 < r; i++) { ok &= !hv[cur[r]][cur[i]]; } if(!ok) break; if(r > 1 && hv[cur[r]][cur[0]]) {r++;break;} r++; } for(int i = 0; i < r; i++) cout << cur[i] << " "; cout << endl; exit(0); } void dfs(int ed) { vis[ed] = 2; auto [st, en] = edges[ed]; cur.push_back(en); for(int i = 1; i <= n; i++) if(i != st && i != en) { if(hv[i][en] && hv[i][st]) continue; if(!hv[en][i]) continue; if(!vis[hv[en][i]-1]) { dfs(hv[en][i]-1); } else if(vis[hv[en][i]-1] == 2) { reverse(all(cur)); while(cur.back() != en) cur.pop_back(); cur.pop_back(); reduce(); } } vis[ed] = 1; cur.pop_back(); } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; edges.resize(m); for(auto &[f, t] : edges) { cin >> f >> t; } for(int i = 0; i < m; i++) edges.push_back({edges[i][1], edges[i][0]}); for(int i = 0; i < 2*m; i++) hv[edges[i][0]][edges[i][1]] = i+1; for(int i = 0; i < 2*m; i++) if(!vis[i]) { cur = {edges[i][0]}; dfs(i); } cout << "no\n"; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 748 KB | Wrong adjacency |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 748 KB | Output is correct |
2 | Correct | 2 ms | 748 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 1644 KB | Output is correct |
2 | Correct | 5 ms | 1644 KB | Output is correct |
3 | Correct | 2 ms | 1772 KB | Output is correct |
4 | Correct | 19 ms | 1796 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1644 KB | Output is correct |
2 | Correct | 10 ms | 1664 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 188 ms | 5752 KB | Output is correct |
2 | Correct | 46 ms | 4816 KB | Output is correct |
3 | Correct | 534 ms | 5880 KB | Output is correct |
4 | Correct | 197 ms | 4816 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 37 ms | 4816 KB | Output is correct |
2 | Correct | 223 ms | 4944 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 43 ms | 4472 KB | Output is correct |
2 | Correct | 326 ms | 5112 KB | Output is correct |
3 | Correct | 17 ms | 6004 KB | Output is correct |
4 | Correct | 844 ms | 6516 KB | Output is correct |