oj.uz

Submission #258203

# Submission time Handle Problem Language Result Execution time Memory
258203 2020-08-05T14:19:24 Z doowey Potemkin cycle (CEOI15_indcyc) C++14
70 / 100
 1000 ms 2256 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1005;
vector<int> T[N];
vector<int> pis[N];
int id[N];
int cc;

void dfs(int u){
    id[u]=cc;
    pis[cc].push_back(u);
    for(auto x : T[u]){
        if(id[x] == -1)
            dfs(x);
    }
}

vector<int> in[N];
bool has[N][N];
int las[N];
int dist[N];
bool mark[N];

int main(){
    fastIO;
    int n, m;
    cin >> n >> m;
    int u, v;
    for(int i = 0 ; i < m ; i ++ ){
        cin >> u >> v;
        T[u].push_back(v);
        T[v].push_back(u);
        has[u][v] = has[v][u] = true;
    }
    int node;
    int low, xi, yi;
    bool good;
    vector<int> ord;
    for(int i = 1; i <= n; i ++ )
        ord.push_back(i);
    random_shuffle(ord.begin(), ord.end());
    for(auto i : ord){
        for(int j = 1; j <= n; j ++ ){
            id[j]=-1;
            in[j].clear();
            pis[j].clear();
            mark[j]=false;
        }
        id[i]=0;
        cc=1;
        for(auto x : T[i]){
            mark[x]=true;
            if(id[x] == -1){
                dfs(x);
                cc ++ ;
            }
        }
        for(auto x : T[i]){
            in[id[x]].push_back(x);
        }
        for(int s = 1; s < cc; s ++ ){
            good = false;
            for(auto x : in[s]){
                for(auto y : in[s]){
                    if(x==y || has[x][y]) continue;
                    good=true;
                }
            }
            if(!good) continue;
            for(auto x : in[s]){
                queue<int> bf;
                bf.push(x);
                for(auto j : pis[s]){
                    las[j]=-1;
                    dist[j]=(int)1e9;
                }
                dist[i]=0;
                dist[x] = 0;
                while(!bf.empty()){
                    node = bf.front();
                    bf.pop();
                    if(mark[node] && dist[node] == 1) continue;
                    if(mark[node] && dist[node] > 0){
                        cout << i << " ";
                        while(1){
                            cout << node << " ";
                            if(node == x) break;
                            node = las[node];
                        }
                        return 0;
                    }
                    for(auto f : T[node]){
                        if(dist[f] > dist[node] + 1){
                            dist[f] = dist[node] + 1;
                            las[f] = node;
                            bf.push(f);
                        }
                    }
                }

            }
        }
    }
    cout << "no\n";
    return 0;
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:48:9: warning: unused variable 'low' [-Wunused-variable]
     int low, xi, yi;
         ^~~
indcyc.cpp:48:14: warning: unused variable 'xi' [-Wunused-variable]
     int low, xi, yi;
              ^~
indcyc.cpp:48:18: warning: unused variable 'yi' [-Wunused-variable]
     int low, xi, yi;
                  ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 544 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 0 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 768 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 81 ms 768 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 34 ms 768 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2048 KB Output is correct
2 Correct 38 ms 1792 KB Output is correct
3 Execution timed out 1085 ms 2048 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 1664 KB Output is correct
2 Execution timed out 1068 ms 1664 KB Time limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 1792 KB Output is correct
2 Correct 202 ms 1792 KB Output is correct
3 Correct 76 ms 2176 KB Output is correct
4 Execution timed out 1077 ms 2256 KB Time limit exceeded