oj.uz

답안 #538350

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
538350 2022-03-16T15:59:10 Z FatihSolak Potemkin cycle (CEOI15_indcyc) C++17
90 / 100
 413 ms 10100 KB 
#include <bits/stdc++.h>
#define N 1005
using namespace std;
int vis[N][N];
bool adj[N][N];
int par[N][N];
int n;
void dfs(int a,int b){
    vis[a][b] = 1;
    //cout << a << " " << b << endl;
    for(int i=1;i<=n;i++){
        if(i != a && adj[b][i] && !adj[a][i]){
            if(vis[b][i] == 1 && i != par[a][b]){
                vector<int> nodes;
                int st = b;
                nodes.push_back(b);
                nodes.push_back(a);
                while(par[a][b] != st){
                    nodes.push_back(par[a][b]);
                    int tmp = b;
                    b = a;
                    a = par[a][tmp];
                }
                for(auto u:nodes){
                    cout << u << " ";
                }
                exit(0);
            }
            else if(!vis[b][i]){
                par[b][i] = a;  
                dfs(b,i);
            }
        }
    }
    vis[a][b] = 2;
}
void solve(){
    int m;
    cin >> n >> m;
    vector<pair<int,int>> edges;
    for(int i=1;i<=m;i++){
        int a,b;
        cin >> a >> b;
        adj[a][b] = adj[b][a] = 1;
        edges.push_back({a,b});
        edges.push_back({b,a});
    }
    for(auto u:edges){
        if(!vis[u.first][u.second]){
            dfs(u.first,u.second);
        }
    }
    cout << "no";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    #ifdef Local
        cout << endl << fixed << setprecision(2) << 1000.0 * clock() / CLOCKS_PER_SEC << " milliseconds.";
    #endif
}
/*
14 15
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 1
4 11
*/

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 276 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 392 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 596 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3028 KB Output is correct
2 Correct 2 ms 2004 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 13 ms 3104 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2132 KB Output is correct
2 Correct 7 ms 2772 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 9284 KB Output is correct
2 Correct 22 ms 7380 KB Output is correct
3 Correct 240 ms 10056 KB Output is correct
4 Correct 74 ms 9676 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 5588 KB Output is correct
2 Correct 115 ms 8764 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 4364 KB Output is correct
2 Correct 135 ms 4144 KB Output is correct
3 Correct 11 ms 2508 KB Output is correct
4 Correct 413 ms 10100 KB Output is correct