Submission #464223

#	Time	Username	Problem	Language	Result	Execution time	Memory
464223		nickmet2004	Potemkin cycle (CEOI15_indcyc)	C++11	80 / 100	380 ms	5192 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];
priority_queue<pair<int,int>> pq;
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;
    pq.push({0 , u});
    while(pq.size()){
        int x = pq.top().second;
        pq.pop();
        for(int y : adj[x]){
            if(X[y] || x == u && y == v)continue;
            if(D[y] > D[x] + 1){
                par[y] = x;
                D[y] = D[x] + 1;
                pq.push({D[y] , 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(500 , (int)edges.size()); ++i){
        q(edges[i].first , edges[i].second);
        if(ok)break;
	}
	if(!ok)cout << "no";

return 0;
}

Compilation message (stderr)

indcyc.cpp: In function 'void q(int, int)':
indcyc.cpp:25:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   25 |             if(X[y] || x == u && y == v)continue;
      |                        ~~~~~~~^~~~~~~~~

• 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: 0 / 10
• Subtask 10: 0 / 10