Submission #171158

#	Time	Username	Problem	Language	Result	Execution time	Memory
171158		Ruxandra985	Potemkin cycle (CEOI15_indcyc)	C++14	80 / 100	1046 ms	6652 KiB

indcyc

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

using namespace std;
vector <int> v[DIMN] , s[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 , p;
    /// cel mai scurt drum de la mch[x].first la mch[x].second
    //swap(mch[x].first , 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;
    sts = 0;
    for (i=0;i<v[mch[x].first].size() - sts - 1;i++){
        vecin = v[mch[x].first][i];
        if ((vecin == mch[x].second) ||
                (ad[mch[x].first][vecin] && ad[mch[x].second][vecin])){
            swap(v[mch[x].first][i] , v[mch[x].first][v[mch[x].first].size()-sts-1]);
            i--;
            sts++;
                }
    }
    //printf ("%d %d\n" , sts , v[mch[x].first].size());

    //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].first)
            p = v[mch[x].first].size()-sts-1;
        else p = v[nod].size()-1;
        for (i=0;i<=p;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){

                    found = 1;
                    break;

                }
                dq.push_back(vecin);
            }
        }
    }
    if (found){
        elem = 0;
        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:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[mch[x].second].size();i++){
              ~^~~~~~~~~~~~~~~~~~~~~~~~
indcyc.cpp:37:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (sts == v[mch[x].second].size())
         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
indcyc.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[mch[x].first].size() - sts - 1;i++){
              ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:97: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: 0 / 10
• Subtask 10: 10 / 10