제출 #205615

#제출 시각아이디문제언어결과실행 시간메모리
205615junodeveloperPotemkin cycle (CEOI15_indcyc)C++14
90 / 100
803 ms11384 KiB
#pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define sz(x) ((int)x.size()) #define all(x) (x).begin(), (x).end() #define pb push_back #define fi first #define se second #define mset(x,y) memset(x,y,sizeof(x)) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repr(i,a,b) for(int i=(a);i>=(b);i--) #ifdef LOCAL #define debug(...) printf(__VA_ARGS__) #else #define debug(...) 1 #endif using namespace __gnu_pbds; using namespace std; using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef vector<int> vi; int n,m; int grp[1010],gc,vis[1010],vc,st,f1,f2; int cnt[1010]; bool chk[1010]; set<int> adj[1010]; bool am[1010][1010]; vi v; void dfs(int u) { if(f1) return; vis[u]=vc; debug("u:%d\n",u); if(chk[u]) { debug("**u:%d\n",u); for(auto& it:v) { if(!am[it][u]) { f1=u,f2=it; } } v.pb(u); return; } for(auto& it:adj[u])if(!vis[it])dfs(it); } void go(int a,int b,int c) { vector<int> d(n+1,-1),par(n+1); queue<int> q; d[b]=0;q.push(b); while(!q.empty()) { int u=q.front();q.pop(); if(chk[u]&&u!=b)continue; for(auto& it:adj[u]) { if(d[it]!=-1||(chk[u]&&chk[it]))continue; d[it]=d[u]+1; par[it]=u; q.push(it); } } for(auto& it:adj[b]) { if(!chk[it])continue; d[it]=0; } vi ans; while(c!=b){ assert(c!=-1); ans.pb(c),c=par[c]; } ans.pb(b);ans.pb(a); for(auto& it:ans)printf("%d ",it); } namespace FIO { using ll=long long; int _curr, _size; char _buff[1<<20]; char rc() { if(_curr == _size) { _size = (int)fread(_buff, 1, sizeof(_buff), stdin); _curr = 0; } if(!_size) return 0; return _buff[_curr++]; } ll ri() { ll c, x = 0, f = 1; while((c = rc()) <= 32); if(c == '-') f = -1, c = rc(); while(c > 32) x = (x << 3) + (x << 1) + c - 48, c = rc(); return x * f; } } using namespace FIO; int main() { int i,j; //scanf("%d%d",&n,&m); n=ri(),m=ri(); for(i=1;i<=m;i++) { int u=ri(),v=ri(); //scanf("%d%d",&u,&v); adj[u].insert(v); adj[v].insert(u); am[u][v]=am[v][u]=true; } for(i=1;i<=n;i++) { chk[i]=true; for(auto& it:adj[i])chk[it]=true; mset(vis,0);vc=0; debug("i:%d\n",i); for(j=1;j<=n;j++) { if(chk[j]||vis[j]) continue; v.clear(); vc++; f1=f2=0; dfs(j); if(f1) { go(i,f1,f2); return 0; } } //chk[i]=false; for(auto& it:adj[i]) { chk[it]=false; adj[it].erase(i); } } puts("no"); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

indcyc.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
indcyc.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
indcyc.cpp: In function 'void dfs(int)':
indcyc.cpp:38:19: warning: statement has no effect [-Wunused-value]
  debug("u:%d\n",u);
                   ^
indcyc.cpp:40:22: warning: statement has no effect [-Wunused-value]
   debug("**u:%d\n",u);
                      ^
indcyc.cpp: In function 'int main()':
indcyc.cpp:113:20: warning: statement has no effect [-Wunused-value]
   debug("i:%d\n",i);
                    ^
#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...