Submission #171123

#	Time	Username	Problem	Language	Result	Execution time	Memory
171123		Ruxandra985	Potemkin cycle (CEOI15_indcyc)	C++14	70 / 100	1070 ms	6120 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;
void ignoree (int x){
    int i , nod , vecin;
    /// cel mai scurt drum de la mch[x].first la mch[x].second
    memset (f , 0 , sizeof(f));
    memset (tt , 0 , sizeof(tt));
    //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();
        if (nod == mch[x].second){
            if (f[mch[x].second] > 3)
                found = 1;
            break;
        }
        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;
                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;
    fscanf (fin,"%d%d",&n,&m);
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d",&mch[i].first,&mch[i].second);
        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: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:57:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d",&n,&m);
     ~~~~~~~^~~~~~~~~~~~~~~~~~
indcyc.cpp:59:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&mch[i].first,&mch[i].second);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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