Submission #42639

#	Time	Username	Problem	Language	Result	Execution time	Memory
42639		nonocut	Potemkin cycle (CEOI15_indcyc)	C++14	30 / 100	1036 ms	5084 KiB

indcyc

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn = 1e3 + 5;
const int inf = 1e9;
int n,m;
int e[maxn][maxn];
int len[maxn], par[maxn];
queue<int> q;
vector<int> way[maxn];
void bfs(int x, int y) {
//    printf("%d -> %d\n",x,y);
    for(int i=1;i<=n;i++) len[i] = inf;
    len[x] = 0; par[x] = 0;
    q.push(x);
    while(!q.empty()) {
        int u = q.front(); q.pop();
//        printf("len %d = %d\n",u,len[u]);
        for(auto v : way[u]) {
            if(u==x && v==y) continue;
            if(len[v]>len[u]+1) {
                len[v] = len[u]+1;
                par[v] = u;
                q.push(v);
            }
        }
    }
//    printf("len %d = %d\n",y,len[y]);
    for(int i=1;i<=n;i++) {
        if(e[i][y] && par[i]!=y && len[i]>=2) {
            printf("%d ",y);
            while(i!=x) {
                printf("%d ",i);
                i = par[i];
            }
            printf("%d",x);
            exit(0);
        }
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) {
        int x, y;
        scanf("%d%d",&x,&y);
        way[x].pb(y); way[y].pb(x);
        e[x][y] = e[y][x] = 1;
    }
    for(int x=1;x<=n;x++) {
        for(int y=x+1;y<=n;y++) {
            if(e[x][y]) {
                bfs(x,y);
            }
        }
    }
    printf("no");
}

Compilation message (stderr)

indcyc.cpp: In function 'int main()':
indcyc.cpp:42:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
indcyc.cpp:45:28: 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