Submission #272901

#TimeUsernameProblemLanguageResultExecution timeMemory
272901MarcoMeijerPotemkin cycle (CEOI15_indcyc)C++14
70 / 100
1096 ms57464 KiB
#include <bits/stdc++.h> using namespace std; // macros typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef pair<ll, ll> lll; typedef tuple<int, int, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<iii> viii; typedef vector<ll> vll; typedef vector<lll> vlll; #define REP(a,b,c) for(int a=int(b); a<int(c); a++) #define RE(a,c) REP(a,0,c) #define RE1(a,c) REP(a,1,c+1) #define REI(a,b,c) REP(a,b,c+1) #define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--) #define FOR(a,b) for(auto& a : b) #define all(a) a.begin(), a.end() #define INF 1e9 #define EPS 1e-9 #define pb push_back #define popb pop_back #define fi first #define se second #define sz size() mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // input template<class T> void IN(T& x) {cin >> x;} template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); } // output template<class T1, class T2> void OUT(const pair<T1,T2>& x); template<class T> void OUT(const T& x) {cout << x;} template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); } template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);} template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); } template<class H> void OUTLS(const H& h) {OUTL(h); } template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); } //===================// // Added libraries // //===================// //===================// //end added libraries// //===================// void program(); int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); program(); } //===================// // begin program // //===================// const int MX = 5e5; int n, m; int a[MX], b[MX]; set<int> adj[MX]; bitset<MX> used; int p[MX], r[MX]; set<int> adjG[MX]; stack<iii> stck; void buildDSU(int dsuSize) { RE(i,dsuSize) p[i]=i, r[i]=0, adjG[i].clear(); while(!stck.empty()) stck.pop(); } int getSet(int i) {return i==p[i]?i:getSet(p[i]);} bool isSameSet(int i, int j) {return getSet(i)==getSet(j);} void unionSet(int i, int j) { i=getSet(i), j=getSet(j); if(r[i] > r[j]) { stck.push({j,i,r[i]}); p[j] = i; } else { p[i] = j; stck.push({i,j,r[j]}); if(r[i] == r[j] && i != j) r[j]++; } } void unionUndo() { int i, j, rj; tie(i,j,rj) = stck.top(); stck.pop(); r[j] = rj; p[i] = i; } vi ans; int par[MX]; bitset<MX> visited; void findShortestPath(int x, int y) { visited.reset(); visited[x] = 1; queue<int> q; q.push(x); while(!q.empty()) { int u = q.front(); q.pop(); FOR(v,adj[u]) if(!visited[v]) { visited[v] = 1; q.push(v); par[v] = u; } } while(y != x) { ans.pb(y); y = par[y]; } ans.pb(x); } void program() { IN(n,m); RE(i,m) { int u, v; IN(u, v); adj[u].insert(v); adj[v].insert(u); a[i] = u; b[i] = v; } RE1(u,n) { // create initial dsu used.reset(); buildDSU(n+1); used[u] = 1; FOR(v,adj[u]) used[v] = 1; RE(i,m) { int u=a[i], v=b[i]; if(used[u] || used[v]) continue; unionSet(u, v); } RE1(i,n) { if(used[i]) continue; FOR(v,adj[i]) { if(!used[v] || v == u) continue; adjG[getSet(i)].insert(v); } } RE1(i,n) FOR(x,adjG[i]) { FOR(y,adjG[i]) { if(adj[x].count(y) || x == y) continue; // found answer used[x] = 0; used[y] = 0; RE1(i,n) adj[i].clear(); RE(i,m) { int u=a[i], v=b[i]; if(used[u] || used[v]) continue; adj[u].insert(v); adj[v].insert(u); } ans.pb(u); findShortestPath(x,y); RE(i,ans.sz) OUT(i==0?"":" ", ans[i]); OUTL(); return; } } } OUTL("no"); }

Compilation message (stderr)

indcyc.cpp: In function 'void program()':
indcyc.cpp:15:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   15 | #define REP(a,b,c) for(int a=int(b); a<int(c); a++)
      |                    ^~~
indcyc.cpp:16:17: note: in expansion of macro 'REP'
   16 | #define RE(a,c) REP(a,0,c)
      |                 ^~~
indcyc.cpp:164:17: note: in expansion of macro 'RE'
  164 |                 RE(i,ans.sz) OUT(i==0?"":" ", ans[i]); OUTL();
      |                 ^~
indcyc.cpp:164:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  164 |                 RE(i,ans.sz) OUT(i==0?"":" ", ans[i]); OUTL();
      |                                                        ^~~~
#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...