oj.uz

Submission #230766

# Submission time Handle Problem Language Result Execution time Memory
230766 2020-05-11T16:39:48 Z nicolaalexandra Potemkin cycle (CEOI15_indcyc) C++14
80 / 100
 1000 ms 6400 KB 
#include <bits/stdc++.h>
#define DIM 1010
#define DIMBUFF 7000000
#define INF 2000000000
using namespace std;

vector <int> L[DIM];
deque <int> sol;
int dist[DIM],t[DIM],a[DIM][DIM],c[DIM];
pair <int,int> mch[DIM*DIM];
int n,m,x,y,i,j,k,ok,pos;
char buff[DIMBUFF];
int bfs (int start){

    for (int i=1;i<=n;i++){
        dist[i] = INF;
        t[i] = 0;
    }
    int p = 1, u = 0;
    c[++u] = start;
    dist[start] = 0;
    int ok = 0, val;

    while (p <= u){
        int nod = c[p];
        p++;
        for (auto vecin : L[nod]){
            if (!a[nod][vecin]) /// nu am muchia asta
                continue;

            if (dist[vecin] == INF){
                dist[vecin] = 1 + dist[nod];
                t[vecin] = nod;

                if (a[vecin][x]){
                    if (dist[vecin] > 1){
                        val = vecin;
                        ok = 1;
                        break;
                    }
                } else c[++u] = vecin;
            }}

        if (ok)
            break;
    }
    if (ok){

        while (val){
            sol.push_back(val);
            val = t[val];
        }
        return 1;
    }
    return 0;
}
int get_nr(){
    while(!(buff[pos] >= '0' && buff[pos] <= '9'))
        pos++;
    int nr = 0;
    while (buff[pos] >= '0' && buff[pos] <= '9'){
        nr = nr*10 + buff[pos] - '0';
        pos++;
    }
    return nr;
}
int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");
    FILE *fin = stdin;
    FILE *fout = stdout;

    //FILE *fin = fopen ("date.in","r");
    //FILE *fout = fopen ("date.out","w");

    fread (buff,1,DIMBUFF,fin);
    //cin>>n>>m;
    n = get_nr(), m = get_nr();
    for (i=1;i<=m;++i){
        //cin>>x>>y;
        x = get_nr(), y = get_nr();
        L[x].push_back(y);
        L[y].push_back(x);
        a[x][y] = a[y][x] = 1;
        mch[i] = make_pair (x,y);
    }

    for (i=1;i<=m;i++){
        x = mch[i].first, y = mch[i].second;
        a[x][y] = a[y][x] = 0;

        if (bfs(y)){ /// am gasit un drum ok
            for (auto it : sol)
                fprintf(fout,"%d ",it);

            fprintf(fout,"%d ",x);

            return 0;
        }

        a[x][y] = a[y][x] = 1;
    }

    fprintf(fout,"no");

    return 0;
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:77:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fread (buff,1,DIMBUFF,fin);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1664 KB Output is correct
2 Correct 6 ms 1664 KB Output is correct
3 Correct 6 ms 1792 KB Output is correct
4 Correct 60 ms 1792 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5760 KB Output is correct
2 Correct 43 ms 5120 KB Output is correct
3 Execution timed out 1093 ms 6016 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4992 KB Output is correct
2 Correct 35 ms 4992 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4736 KB Output is correct
2 Correct 199 ms 4736 KB Output is correct
3 Correct 299 ms 6272 KB Output is correct
4 Execution timed out 1097 ms 6400 KB Time limit exceeded