Submission #79052

#TimeUsernameProblemLanguageResultExecution timeMemory
79052dualityPotemkin cycle (CEOI15_indcyc)C++11
100 / 100
67 ms7196 KiB
#define DEBUG 0 #include <bits/stdc++.h> using namespace std; #if DEBUG // basic debugging macros int __i__,__j__; #define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl #define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl #define printVar(n) cout<<#n<<": "<<n<<endl #define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl #define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;} #define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;} // advanced debugging class // debug 1,2,'A',"test"; class _Debug { public: template<typename T> _Debug& operator,(T val) { cout << val << endl; return *this; } }; #define debug _Debug(), #else #define printLine(l) #define printLine2(l,c) #define printVar(n) #define printArr(a,l) #define print2dArr(a,r,c) #define print2dArr2(a,r,c,l) #define debug #endif // define #define MAX_VAL 999999999 #define MAX_VAL_2 999999999999999999LL #define EPS 1e-6 #define mp make_pair #define pb push_back // typedef typedef unsigned int UI; typedef long long int LLI; typedef unsigned long long int ULLI; typedef unsigned short int US; typedef pair<int,int> pii; typedef pair<LLI,LLI> plli; typedef vector<int> vi; typedef vector<LLI> vlli; typedef vector<pii> vpii; typedef vector<plli> vplli; // ---------- END OF TEMPLATE ---------- vi adjList[1000]; int order[1000],deg[1000]; priority_queue<pii> H; set<int> S[1000]; int no[1000],parent[1000]; queue<int> Q; int main() { int i; int N,R; int a,b; scanf("%d %d",&N,&R); for (i = 0; i < R; i++) { scanf("%d %d",&a,&b); a--,b--; adjList[a].pb(b); adjList[b].pb(a); } int j,c; a = -1; for (i = 0; i < N; i++) order[i] = -1,H.push(mp(0,i)); for (i = 0; i < N; i++) { while (order[H.top().second] != -1) H.pop(); int u = H.top().second,p = -1; H.pop(); order[u] = i; for (j = 0; j < adjList[u].size(); j++) { int v = adjList[u][j]; if (order[v] != -1) { S[u].insert(v); if ((p == -1) || (order[v] > order[p])) p = v; } else H.push(mp(++deg[v],v)); } if (p != -1) { for (auto it = S[u].begin(); it != S[u].end(); it++) { if ((*it != p) && !S[p].count(*it)) { a = u,b = p,c = *it; break; } } } if (a != -1) break; } if (a == -1) printf("no\n"); else { fill(parent,parent+N,-1); for (i = 0; i < adjList[a].size(); i++) { if (adjList[a][i] != c) no[adjList[a][i]] = 1; } no[a] = 1; Q.push(b); while (!Q.empty()) { int u = Q.front(); Q.pop(); if (u == c) break; for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if ((parent[v] == -1) && !no[v]) { parent[v] = u; Q.push(v); } } } printf("%d",a+1); while (c != b) printf(" %d",c+1),c = parent[c]; printf(" %d\n",b+1); } return 0; }

Compilation message (stderr)

indcyc.cpp: In function 'int main()':
indcyc.cpp:84:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < adjList[u].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~~~~
indcyc.cpp:105:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < adjList[a].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~
indcyc.cpp:115:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (i = 0; i < adjList[u].size(); i++) {
                         ~~^~~~~~~~~~~~~~~~~~~
indcyc.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&N,&R);
     ~~~~~^~~~~~~~~~~~~~~
indcyc.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~~
indcyc.cpp:114:13: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
             if (u == c) break;
             ^~
#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...