Submission #171113

#	Time	Username	Problem	Language	Result	Execution time	Memory
171113		Ruxandra985	Potemkin cycle (CEOI15_indcyc)	C++14	30 / 100	476 ms	6392 KiB

indcyc

#include <bits/stdc++.h>
#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));
    ok[mch[x].first][mch[x].second] = 1;
    ok[mch[x].second][mch[x].first] = 1;
    for (i=1;i<=n;i++){
        if (ad[mch[x].first][i] && ad[mch[x].second][i]){
            ok[mch[x].first][i] = ok[mch[x].second][i] = 1;
            ok[i][mch[x].first] = ok[i][mch[x].second] = 1;
        }
    }
    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 (ok[nod][vecin])
                continue;
            if (!f[vecin]){
                f[vecin] = 1 + f[nod];
                tt[vecin] = nod;
                dq.push_back(vecin);
            }
        }
    }
    ok[mch[i].first][mch[i].second] = 0;
    ok[mch[i].second][mch[i].first] = 0;
    for (i=1;i<=n;i++){
        if (ad[mch[x].first][i] && ad[mch[x].second][i]){
            ok[mch[x].first][i] = ok[mch[x].second][i] = 0;
            ok[i][mch[x].first] = ok[i][mch[x].second] = 0;
        }
    }
    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:34: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:66: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:68: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: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10