Submission #230764

#	Time	Username	Problem	Language	Result	Execution time	Memory
230764		nicolaalexandra	Potemkin cycle (CEOI15_indcyc)	C++14	70 / 100	1095 ms	6016 KiB

indcyc

#include <bits/stdc++.h>
#define DIM 1010
#define DIMBUFF 7000000
#define INF 2000000000
using namespace std;

vector <int> L[DIM];
deque <int> c,sol,w;
int dist[DIM],t[DIM],a[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;
    }
    c.clear(), sol.clear();
    c.push_back(start);
    dist[start] = 0;
    int ok = 0, x;

    while (!c.empty()){
        int nod = c.front();
        c.pop_front();
        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][i]){
                    if (dist[vecin] > 1){
                        x = vecin;
                        ok = 1;
                        break;
                    }
                } else c.push_back(vecin);
            }}

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

        while (x){
            sol.push_back(x);
            x = t[x];
        }
        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;

    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;
    }

    for (i=1;i<=n;++i){
        if (L[i].size() < 2)
            continue;

        for (auto x : L[i]){
            //L[i].erase(x), L[x].erase(i);
            a[i][x] = a[x][i] = 0;
            if (bfs(x)){ /// am gasit un drum ok
                for (auto it : sol)
                    fprintf(fout,"%d ",it);

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

                return 0;
            }
            //L[i].insert(x), L[x].insert(i);
            a[i][x] = a[x][i] = 1;
        }
    }


    fprintf(fout,"no");

    return 0;
}

Compilation message (stderr)

indcyc.cpp: In function 'int main()':
indcyc.cpp:73: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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10