Submission #230753

#	Time	Username	Problem	Language	Result	Execution time	Memory
230753		nicolaalexandra	Potemkin cycle (CEOI15_indcyc)	C++14	60 / 100	1092 ms	10104 KiB

indcyc

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

set <int> L[DIM];
deque <int> c,sol,w;

int n,m,x,y,i,j,k,ok;
int dist[DIM],t[DIM];

int bfs (int start, int dest){

    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;
    while (!c.empty()){
        int nod = c.front();
        c.pop_front();
        for (auto vecin : L[nod]){
            if (L[vecin].find(i) != L[vecin].end())
                continue;
            if (dist[vecin] == INF){
                dist[vecin] = 1 + dist[nod];
                t[vecin] = nod;
                if (vecin == dest){
                    ok = 1;
                    break;
                }
                c.push_back(vecin);
            }}}
    if (ok){
        int x = dest;
        while (x){
            sol.push_back(x);
            x = t[x];
        }
        return 1;
    }
    return 0;
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;
    for (i=1;i<=m;i++){
        cin>>x>>y;
        L[x].insert(y);
        L[y].insert(x);
    }

    for (i=1;i<=n;i++){
        w.clear();
        for (auto it : L[i])
            w.push_back(it);
        for (j=0;j<w.size();j++){
            x = w[j];
            for (k=j+1;k<w.size();k++){
                y = w[k];
                if (L[x].find(y) != L[x].end())
                    continue;
                /// incerc sa gasesc cel mai scurt drum de la x la y care nu trece prin i
                L[i].erase(x), L[x].erase(i);
                L[i].erase(y), L[y].erase(i);

                if (bfs(x,y)){ /// am gasit un drum
                    for (auto it : sol)
                        cout<<it<<" ";
                    cout<<i;

                    return 0;
                }

                L[i].insert(x), L[x].insert(i);
                L[i].insert(y), L[y].insert(i);
            }
        }
    }


    cout<<"no";

    return 0;
}

Compilation message (stderr)

indcyc.cpp: In function 'int main()':
indcyc.cpp:65:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j=0;j<w.size();j++){
                  ~^~~~~~~~~
indcyc.cpp:67:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (k=j+1;k<w.size();k++){
                        ~^~~~~~~~~

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