oj.uz

Submission #464313

# Submission time Handle Problem Language Result Execution time Memory
464313 2021-08-12T21:56:19 Z nickmet2004 Potemkin cycle (CEOI15_indcyc) C++11
100 / 100
 954 ms 5964 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];
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(5690 , (int)edges.size()); ++i){
        q(edges[i].first , edges[i].second);
        if(ok)break;
	}
	if(!ok)cout << "no";
 }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 352 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 332 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 2 ms 716 KB Output is correct
2 Correct 9 ms 716 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1612 KB Output is correct
2 Correct 2 ms 1612 KB Output is correct
3 Correct 4 ms 1612 KB Output is correct
4 Correct 75 ms 1696 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1612 KB Output is correct
2 Correct 83 ms 1616 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5576 KB Output is correct
2 Correct 8 ms 4940 KB Output is correct
3 Correct 601 ms 5632 KB Output is correct
4 Correct 330 ms 4964 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 4940 KB Output is correct
2 Correct 954 ms 4940 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4580 KB Output is correct
2 Correct 35 ms 4396 KB Output is correct
3 Correct 43 ms 5956 KB Output is correct
4 Correct 587 ms 5964 KB Output is correct