oj.uz

Submission #464232

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

return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1612 KB Output is correct
2 Correct 3 ms 1612 KB Output is correct
3 Correct 11 ms 1612 KB Output is correct
4 Correct 71 ms 1652 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1616 KB Output is correct
2 Correct 81 ms 1592 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5192 KB Output is correct
2 Correct 9 ms 4812 KB Output is correct
3 Correct 530 ms 5188 KB Output is correct
4 Correct 306 ms 4812 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 812 ms 4704 KB Output is correct
2 Correct 882 ms 4684 KB Output is correct

Subtask #10
0 / 10.0

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