제출 #204516

#제출 시각아이디문제언어결과실행 시간메모리
204516junodeveloperPotemkin cycle (CEOI15_indcyc)C++14
30 / 100
1127 ms526664 KiB
#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; int cnt[1010]; bool chk[1010]; vi adj[1010]; void dfs(int u) { grp[u]=gc; for(auto& it:adj[u])if(!grp[it]&&(!chk[u]||!chk[it]))dfs(it); } void go(int a,int b) { 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; } int e=-1; for(auto& it:adj[a]) if(d[it]>0) e=it; vi ans; while(e!=b)ans.pb(e),e=par[e]; ans.pb(b);ans.pb(a); for(auto& it:ans)printf("%d ",it); } int main() { int i,j; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); adj[u].pb(v); adj[v].pb(u); } for(i=1;i<=n;i++) { mset(grp,0);gc=0; chk[i]=true; for(auto& it:adj[i])chk[it]=true; for(auto& it:adj[i])if(!grp[it]) { gc++; dfs(it); } for(j=1;j<=gc;j++)cnt[j]=0; for(auto& it:adj[i])cnt[grp[it]]++; for(auto& it:adj[i]){ int c=0; for(auto& jt:adj[it]) { if(chk[jt]&&grp[it]==grp[jt])c++; } if(c!=cnt[grp[it]]-1) { go(i,it); return 0; } } chk[i]=false; for(auto& it:adj[i])chk[it]=false; } puts("no"); return 0; }

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

indcyc.cpp: In function 'int main()':
indcyc.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
indcyc.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~
#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...