oj.uz

Submission #42639

# Submission time Handle Problem Language Result Execution time Memory
42639 2018-03-01T17:02:28 Z nonocut Potemkin cycle (CEOI15_indcyc) C++14
30 / 100
 1000 ms 5084 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 1 ms 496 KB Output is correct
5 Correct 1 ms 516 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 548 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 988 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1756 KB Wrong answer on graph without induced cycle
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1760 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 5084 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 5084 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1036 ms 5084 KB Time limit exceeded
2 Halted 0 ms 0 KB -