Submission #464293

#	Time	Username	Problem	Language	Result	Execution time	Memory
464293		nickmet2004	Potemkin cycle (CEOI15_indcyc)	C++11	100 / 100	984 ms	5448 KiB

indcyc

#include<bits/stdc++.h>
 
using namespace std;
const int N = 1005;
int n , m;
int F[N][N] , X[N] , par[N];
vector<pair<int , int>> edges;
vector<int> adj[N];
queue<int> Q;
int ok;
int D[N];
void q(int u, int v){
    memset(X , 0 , sizeof(X));
    memset(par ,0 , sizeof(par));
    for(int i = 1; i <= n; ++i){
        if(F[i][u] && F[i][v]) X[i] = 1;
    }
    for(int i = 1; i<= n; ++i) D[i] = 2e9;
    D[u] =0;
    Q.push(u);
    while(Q.size()){
        int x = Q.front();
        Q.pop();
        for(int y : adj[x]){
            if(X[y] || (x == u && y == v))continue;
            if(D[y] > D[x] + 1){
                D[y] = D[x] + 1;
                par[y] = x;
                Q.push(y);
            }
        }
    }
    if(D[v] == 2e9) return;
    int U= v;
    while(1){
        cout << U << " ";
        if(U == u)break;
        U = par[U];
    }
    ok = 1;
}
int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    int u ,v;
    for(int i= 0; i< m; ++i){
        cin >> u >> v;
        F[u][v] = 1; F[v][u] = 1;
        adj[u].emplace_back(v); adj[v].emplace_back(u);
        edges.emplace_back(u , v);
    }
    mt19937 rng(time(0));
	shuffle(edges.begin() , edges.end() , rng);
	//for(auto x : edges)cout << x.first << " " << x.second<<endl;
	for(int i = 0; i < min(5700 , (int)edges.size()); ++i){
        q(edges[i].first , edges[i].second);
        if(ok)break;
	}
	if(!ok)cout << "no";
 }

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10