Submission #781851

#	Time	Username	Problem	Language	Result	Execution time	Memory
781851		Charizard2021	Potemkin cycle (CEOI15_indcyc)	C++17	0 / 100	1087 ms	1360 KiB

indcyc

#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;
        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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10