Submission #171225

#TimeUsernameProblemLanguageResultExecution timeMemory
171225Ruxandra985Potemkin cycle (CEOI15_indcyc)C++14
100 / 100
985 ms6112 KiB
#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);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...