oj.uz

Submission #781854

# Submission time Handle Problem Language Result Execution time Memory
781854 2023-07-13T12:00:50 Z Charizard2021 Potemkin cycle (CEOI15_indcyc) C++17
0 / 100
 1000 ms 579468 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1001;
int n, r;
int adjBool[N][N];
vector<int> adj[N];
vector<set<int> > cmp_list;
vector<int> works, cmp;
int cnt_cmp;
void dfs_cmp(int u, int cur){
    cmp[u] = cur;
    for(int v : adj[u]){
        if(works[v] == 2 && cmp[v] == -1){
            dfs_cmp(v, u);
        }
    }
}
vector<int> pre;
void bfs_ans (int a, int b){
    queue<int> q;
    q.push(a);
    pre[a] = -2;
    while (q.size()){
        int u = q.front();
        q.pop();
        for (int v : adj[u]){
            if (works[v] == 2 && pre[v] == -1){
                pre[v] = v;
                q.push(v);
            }
        }
    }
}
int main(){
    cin >> n >> r;
    for (int i = 0; i < r; i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        adjBool[a][b] = adjBool[b][a] = 1;
    }
    for (int root = 1; root <= n; root++){
        works.assign(n + 1, 2);
        works[root] = 0;
        for(int v : adj[root]){
            works[v] = 1;
        }
        cmp.assign(n + 1, -1);
        cnt_cmp = 0;
        cmp_list.clear();
        for (int i = 1; i <= n; i++){
            if (works[i] == 2 && cmp[i] == -1){
                cmp_list.push_back({});
                dfs_cmp( i, cnt_cmp++ );
            }
        }
        for (int v : adj[root]){
            for (int v2 : adj[v]){
                if (v2 != root && works[v2] == 2){
                    cmp_list[cmp[v2]].insert(v);
                }
            }
        }
        int ansu = -1, ansv = -1;
        for (int i = 0; i < cnt_cmp; i++){
            for (int u : cmp_list[i]){
                for (int v : cmp_list[i]){
                    if (u != v && !adjBool[u][v]){
                        ansu = u, ansv = v;
                        break;
                    }
                    if (ansu != -1){
                        break;
                    }
                }
            }
            if (ansu != -1){
                break;
            }
        }
        if (ansu != -1){
            cout << root << " ";
            works[ansu] = 2;
            works[ansv] = 2;
            pre.assign(n + 1, -1);
            bfs_ans(ansu, ansv);
            vector<int> path;
            path.push_back(ansv);
            while(ansv != ansu){
                ansv = pre[ansv];
                path.push_back(ansv);
            }
            reverse( path.begin(), path.end() );
            for(int i = 0; i < (int)path.size(); i++){
                cout << path[i] << " ";
            }
            cout << "\n";
            return 0;
        }
    }
    cout << "no\n";
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1106 ms 579468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1236 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1236 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 1492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 2900 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 9940 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 8988 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 6680 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -