Submission #136594

#	Time	Username	Problem	Language	Result	Execution time	Memory
136594		thebes	Potemkin cycle (CEOI15_indcyc)	C++14	30 / 100	6 ms	1400 KiB

indcyc

#include <bits/stdc++.h>
using namespace std;

const int MN = 1005, LG = 12;
int n, m, i, x, y, vis[MN], d[MN], p[MN], sp[MN][LG], t[MN][2], nxt, rev[MN];
pair<int,int> e[MN];
vector<int> adj[MN], ee[MN], eee[MN], tt[MN], ans;
queue<int> q;
set<pair<int,int>> done;

void dfs(int n,int p){
    t[n][0] = ++nxt; rev[nxt] = n;
    sp[n][0] = p;
    for(auto v : tt[n])
        dfs(v, n);
    t[n][1] = nxt;
}

int anc(int x,int y){
    if(d[x]<d[y]) swap(x,y);
    for(int i=LG-1;i>=0;i--){
        if((1<<i)<=d[x]-d[y])
            x = sp[x][i];
    }
    if(x==y) return x;
    for(int i=LG-1;i>=0;i--){
        if(sp[x][i]!=sp[y][i]){
            x=sp[x][i];
            y=sp[y][i];
        }
    }
    return sp[x][0];
}

bool solve(int l,int r){
    if(done.count({l,r})) return 0;
    done.insert({l,r}); int f=0;
    if(ee[l][0]<r&&solve(l,ee[l][0])) return 1;
    else if(ee[l][0]<r) f=1;
    if(eee[r].back()>l&&solve(eee[r].back(),r)) return 1;
    else if(eee[r].back()>l) f=1;
    int x = anc(rev[l], rev[r]);
    if(d[rev[l]]+d[rev[r]]-2*d[x]>=3&&!f){
        memset(p,0,sizeof(p));
        q.push(rev[l]); p[rev[l]]=-1;
        while(q.size()){
            x = q.front(); q.pop();
            for(auto v : tt[x]){
                if(!p[v]){
                    p[v] = x;
                    q.push(v);
                }
            }
            if(sp[x][0]&&!p[sp[x][0]]){
                p[sp[x][0]] = x;
                q.push(sp[x][0]);
            }
            for(auto v : ee[t[x][0]]){
                if(v==r&&x==rev[l]) continue;
                if(!p[rev[v]]){
                    p[rev[v]] = x;
                    q.push(rev[v]);
                }
            }
        }
        x = rev[r];
        while(~x){
            ans.push_back(x);
            x = p[x];
        }
        return 1;
    }
}

int main(){
    for(scanf("%d%d",&n,&m),i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        adj[x].push_back(y);
        adj[y].push_back(x);
        e[i]={x,y};
    }
    q.push(1); vis[1]=1;
    while(q.size()){
        x = q.front(); q.pop();
        for(auto v : adj[x]){
            if(!vis[v]){
                vis[v]=1; d[v]=d[x]+1; p[v]=x;
                q.push(v);
            }
        }
        if(p[x]){
            adj[p[x]].erase(find(adj[p[x]].begin(),adj[p[x]].end(),x));
            adj[x].erase(find(adj[x].begin(),adj[x].end(),p[x]));
        }
        tt[p[x]].push_back(x);
    }
    dfs(1,0);
    for(int j=1;j<LG;j++){
        for(i=1;i<=n;i++)
            sp[i][j]=sp[sp[i][j-1]][j-1];
    }
    for(i=1;i<=n;i++){
        for(auto v : adj[rev[i]]){
            if(t[v][0]>=i) ee[i].push_back(t[v][0]);
            else eee[i].push_back(t[v][0]);
        }
    }
    for(i=1;i<=n;i++){
        sort(ee[i].begin(),ee[i].end());
        sort(eee[i].begin(),eee[i].end());
    }
    for(i=1;i<=n;i++){
        for(auto v : ee[i]){
            if(solve(i,v)) break;
        }
        if(ans.size()) break;
        for(auto v : eee[i]){
            if(solve(v,i)) break;
        }
        if(ans.size()) break;
    }
    if(ans.size()){
        for(auto v : ans) printf("%d ",v);
        printf("\n");
    }
    else printf("no\n");
    return 0;
}

Compilation message (stderr)

indcyc.cpp: In function 'bool solve(int, int)':
indcyc.cpp:73:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
indcyc.cpp: In function 'int main()':
indcyc.cpp:76:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%d%d",&n,&m),i=1;i<=m;i++){
         ~~~~~~~~~~~~~~~~~~~^~~~
indcyc.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10