oj.uz

Submission #464218

# Submission time Handle Problem Language Result Execution time Memory
464218 2021-08-12T14:26:49 Z nickmet2004 Potemkin cycle (CEOI15_indcyc) C++11
70 / 100
 1000 ms 5564 KB 
#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(5000 , (int)edges.size()); ++i){
        q(edges[i].first , edges[i].second);
        if(ok)break;
	}
	if(!ok)cout << "no";

return 0;
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 17 ms 788 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 1632 KB Output is correct
2 Correct 3 ms 1612 KB Output is correct
3 Correct 3 ms 1636 KB Output is correct
4 Correct 318 ms 1612 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 1624 KB Output is correct
2 Correct 211 ms 1616 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5564 KB Output is correct
2 Correct 19 ms 4940 KB Output is correct
3 Execution timed out 1097 ms 5552 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 4940 KB Output is correct
2 Execution timed out 1091 ms 4940 KB Time limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 4572 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -