oj.uz

Submission #258195

# Submission time Handle Problem Language Result Execution time Memory
258195 2020-08-05T14:10:14 Z doowey Potemkin cycle (CEOI15_indcyc) C++14
80 / 100
 1000 ms 2688 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];
int id[N];
int cc;

void dfs(int u){
    id[u]=cc;
    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;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ ){
            id[j]=-1;
            in[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 ++ ){
            low = (int)1e9, xi = -1, yi = -1;
            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(int j = 1; j <= n; j ++ ){
                    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:46:9: warning: variable 'low' set but not used [-Wunused-but-set-variable]
     int low, xi, yi;
         ^~~
indcyc.cpp:46:14: warning: variable 'xi' set but not used [-Wunused-but-set-variable]
     int low, xi, yi;
              ^~
indcyc.cpp:46:18: warning: variable 'yi' set but not used [-Wunused-but-set-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 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 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 6 ms 512 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 768 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 76 ms 888 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2304 KB Output is correct
2 Correct 20 ms 1920 KB Output is correct
3 Execution timed out 1087 ms 2304 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1792 KB Output is correct
2 Correct 837 ms 1868 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 2468 KB Output is correct
2 Correct 176 ms 2560 KB Output is correct
3 Correct 168 ms 2688 KB Output is correct
4 Execution timed out 1091 ms 2688 KB Time limit exceeded