Submission #171225

#	Time	Username	Problem	Language	Result	Execution time	Memory
171225		Ruxandra985	Potemkin cycle (CEOI15_indcyc)	C++14	100 / 100	985 ms	6112 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 dont[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));
    tt[mch[x].first] = 0;
    for (i=0;i<v[mch[x].second].size();++i){
        vecin = v[mch[x].second][i];
        if (ad[mch[x].first][vecin] && ad[mch[x].second][vecin])
            sts++;
    }
    //printf ("%d %d\n",sts , v[mch[x].second].size());
    if (sts == v[mch[x].second].size())
        return;

    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 (vecin == mch[x].second && nod != mch[x].first){
                f[vecin] = 1 + f[nod];
                tt[vecin] = nod;
                found = 1;
                break;
            }
            if (ad[mch[x].first][vecin] && ad[mch[x].second][vecin]){
                if (vecin != mch[x].second)
                    f[vecin] = 2;
            }
            else 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];
        }
    }
}
void ignore_node (int x){
    int i , nod , vecin , sts = 0 , j , vecin1 , vecin2 , sf;
    /// cel mai scurt drum de la mch[x].first la mch[x].second
    if (found)
        return;
    memset (f , 0 , sizeof(f));
    tt[x] = 0;
    for (i=0;i<v[x].size();++i){
        for (j=i+1;j<v[x].size();j++){
            vecin1 = v[x][i];
            vecin2 = v[x][j];
            if (ad[vecin1][vecin2]){
                dont[ad[x][vecin1]] = x;
                dont[ad[x][vecin2]] = x;
                dont[ad[vecin2][vecin1]] = x;
            }
        }
    }
    //printf ("%d %d\n",sts , v[mch[x].second].size());

    dq.clear();
    dq.push_back(x);
    f[x] = 1;
    while (!dq.empty()){
        nod = dq.front();
        dq.pop_front();
        if (found)
            break;
        for (i=0;i<v[nod].size();++i){
            vecin = v[nod][i];
            if (dont[ad[nod][vecin]] == x){
                if (vecin == x){
                    found = 1;
                    //f[vecin] = 1 + f[nod];
                    //tt[vecin] = nod;
                    sf = nod;
                    break;
                }
            }
            else if (!f[vecin]){
                f[vecin] = 1 + f[nod];
                tt[vecin] = nod;
                dq.push_back(vecin);
            }

        }
    }
    if (found){
        nod = sf;
        while (nod){
            sol[++elem] = nod;
            nod = tt[nod];
        }
    }
}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int i , vecin1 , vecin2;
    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] = i;
        ad[mch[i].second][mch[i].first] = i;
        ad[mch[i].second][mch[i].second] = 1;
        ad[mch[i].first][mch[i].first] = 1;
    }
    int ok = 0 , mom;
    for (int x=1;x<=n;x++){
        mom = 1;
        for (i=0;i<v[x].size();++i){
            for (int j=i+1;j<v[x].size();j++){
                vecin1 = v[x][i];
                vecin2 = v[x][j];
                if (ad[vecin1][vecin2]){
                    mom = 0;
                }
            }
        }
        ok = (ok + mom);

    }
    if (ok == 1 && n > 300){
        for (i=1;i<=n;i++){
            //printf ("%d ",i);
            ignore_node(i);
            if (found)
                break;
        }
    }
    else {
        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:30:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[mch[x].second].size();++i){
              ~^~~~~~~~~~~~~~~~~~~~~~~~
indcyc.cpp:36:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (sts == v[mch[x].second].size())
         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
indcyc.cpp:45:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[nod].size();++i){
                  ~^~~~~~~~~~~~~~
indcyc.cpp: In function 'void ignore_node(int)':
indcyc.cpp:79:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[x].size();++i){
              ~^~~~~~~~~~~~
indcyc.cpp:80:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j=i+1;j<v[x].size();j++){
                    ~^~~~~~~~~~~~
indcyc.cpp:100:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[nod].size();++i){
                  ~^~~~~~~~~~~~~~
indcyc.cpp:73:27: warning: unused variable 'sts' [-Wunused-variable]
     int i , nod , vecin , sts = 0 , j , vecin1 , vecin2 , sf;
                           ^~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:148:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[x].size();++i){
                  ~^~~~~~~~~~~~
indcyc.cpp:149:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j=i+1;j<v[x].size();j++){
                            ~^~~~~~~~~~~~
indcyc.cpp:132: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: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10