Submission #171138

#	Time	Username	Problem	Language	Result	Execution time	Memory
171138		Ruxandra985	Potemkin cycle (CEOI15_indcyc)	C++14	90 / 100	1076 ms	6152 KiB

indcyc

#include <bits/stdc++.h>
#pragma GCC optimize "Ofast"
#define DIMN 1010

using namespace std;
vector <int> v[DIMN];
int tt[DIMN] , f[DIMN] , sol[DIMN] , ad[DIMN][DIMN] , ok[DIMN][DIMN];
pair <int,int> mch[100010];
int elem , found , n , m;
deque <int> dq;
char buff[2000000];
int poz = 0;
int getnr(){
    int nr = 0;

    while ('0' > buff[poz] || buff[poz] > '9')
        poz++;
    while ('0' <= buff[poz] && buff[poz] <= '9'){
        nr = nr * 10 + buff[poz] - '0';
        poz++;
    }
    return nr;
}
void ignoree (int x){
    int i , nod , vecin , sts = 0;
    /// cel mai scurt drum de la mch[x].first la mch[x].second
    memset (f , 0 , sizeof(f));
    memset (tt , 0 , sizeof(tt));
    for (i=0;i<v[mch[x].second].size();i++){
        vecin = v[mch[x].second][i];
        if ((vecin == mch[x].first) ||
                (ad[mch[x].first][vecin] && ad[mch[x].second][vecin]))
            sts++;
    }
    if (sts == v[mch[x].second].size())
        return;

    //if (x == 2)
      //  printf ("a");
    dq.clear();
    dq.push_back(mch[x].first);
    f[mch[x].first] = 1;
    while (!dq.empty()){
        nod = dq.front();
        dq.pop_front();
        for (i=0;i<v[nod].size();i++){
            vecin = v[nod][i];
            if ((nod == mch[x].first && vecin == mch[x].second) ||
                (ad[mch[x].first][vecin] && ad[mch[x].second][vecin])){
                if (vecin != mch[x].second)
                    f[vecin] = 2;
                continue;
            }
            if (!f[vecin]){
                f[vecin] = 1 + f[nod];
                tt[vecin] = nod;
                if (vecin == mch[x].second){

                    if (f[mch[x].second] > 3)
                        found = 1;
                    break;

                }
                dq.push_back(vecin);
            }
        }
    }
    if (found){
        nod = mch[x].second;
        while (nod){
            sol[++elem] = nod;
            nod = tt[nod];
        }
    }
}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int i;
    fread (buff , 1 , 2000000 , fin);
    n = getnr();
    m = getnr();
    for (i=1;i<=m;i++){
        mch[i].first = getnr();
        mch[i].second = getnr();
        v[mch[i].first].push_back(mch[i].second);
        v[mch[i].second].push_back(mch[i].first);
        ad[mch[i].first][mch[i].second] = 1;
        ad[mch[i].second][mch[i].first] = 1;
    }
    for (i=1;i<=m;i++){
        /// daca ignoram muchia i
        ignoree (i);
        if (found)
            break;
    }
    if (!found)
        fprintf (fout,"no");
    else {
        for (i=1;i<=elem;i++)
            fprintf (fout,"%d ",sol[i]);
    }
    return 0;
}

Compilation message (stderr)

indcyc.cpp: In function 'void ignoree(int)':
indcyc.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[mch[x].second].size();i++){
              ~^~~~~~~~~~~~~~~~~~~~~~~~
indcyc.cpp:35:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (sts == v[mch[x].second].size())
         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
indcyc.cpp:46:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:81: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 , 2000000 , 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: 10 / 10
• Subtask 10: 10 / 10