제출 #832560

#제출 시각아이디문제언어결과실행 시간메모리
832560Kaitokid수천개의 섬 (IOI22_islands)C++17
5 / 100
29 ms11472 KiB
#include <bits/stdc++.h> using namespace std; int dg[100009]; vector<int>to[100009],frm[100009]; int ed[200009][2]; bool incy[200009],vsnd[200009],dl[200009]; vector<int>tocy[2],cy[2]; bool fnd; void dfs(int x,int u) { //cout<<x<<" "<<tocy[u].back()<<" "<<u<<endl; if(fnd||(vsnd[x]==2))return; if(vsnd[x]==1) { fnd=true; while(ed[tocy[u].back()][0]!=x){cy[u].push_back(tocy[u].back());tocy[u].pop_back();} cy[u].push_back(tocy[u].back());tocy[u].pop_back(); reverse(cy[u].begin(),cy[u].end()); return; } vsnd[x]=1; for(auto v:frm[x]) {if(!dl[ed[v][1]]){tocy[u].push_back(v);dfs(ed[v][1],u);if(fnd)return ;tocy[u].pop_back();}} vsnd[x]=2; } variant<bool,vector<int> > find_journey(int N, int M, vector<int> U, vector<int> V) { for(int i=0;i<M;i++) { ed[i][0]=U[i]; ed[i][1]=V[i]; frm[U[i]].push_back(i); to[V[i]].push_back(i); dg[U[i]]++; } queue<int>qq; for(int i=0;i<N;i++) if(dg[i]==0)qq.push(i); while(!qq.empty()) { int u=qq.front(); qq.pop(); dl[u]=1; for(auto v:to[u]) { dg[ed[v][0]]--; if(dg[ed[v][0]]==0)qq.push(ed[v][0]); } } if(dl[0])return false; int h=0,u=-1,v=-1; vector<int>gg; while(true) { qq.push(h); while(!qq.empty()) { int uu=qq.front(); qq.pop(); dl[uu]=1; for(auto vv:to[uu]) { dg[ed[vv][0]]--; if((!dl[ed[vv][0]])&&dg[ed[vv][0]]==0)qq.push(ed[vv][0]); } } vector<int>bb; for(auto w:frm[h]) if((!dl[ed[w][1]]))bb.push_back(w); if(bb.empty())return false; if(bb.size()==1) { gg.push_back(bb[0]); h=ed[bb[0]][1]; continue; } u=bb[0],v=bb[1]; break; } dl[h]=0; vsnd[h]=1; tocy[0].push_back(u); fnd=false; dfs(ed[u][1],0); memset(vsnd,0,sizeof vsnd); fnd=false; vsnd[h]=1; tocy[1].push_back(v); dfs(ed[v][1],1); /*cout<<h<<' '<<u<<" "<<v<<" "<<ed[u][1]<<" "<<ed[v][1]<<endl; cout<<"to "; for(auto w:gg)cout<<w<<" "; cout<<endl; cout<<"tocy0 "; for(auto w:tocy[0])cout<<w<<" "; cout<<endl; cout<<"cy0 "; for(auto w:cy[0])cout<<w<<" "; cout<<endl; cout<<"tocy1 "; for(auto w:tocy[1])cout<<w<<" "; cout<<endl; cout<<"cy1 "; for(auto w:cy[1])cout<<w<<" "; cout<<endl; // return {-1};*/ // if((cy[0].empty())||(cy[1].empty()))return false; vector<int>ans=gg; for(auto w:tocy[0])ans.push_back(w); for(auto w:cy[0]){ans.push_back(w);incy[w]=1;} reverse(tocy[0].begin(),tocy[0].end()); for(auto w:tocy[0])ans.push_back(w); reverse(tocy[0].begin(),tocy[0].end()); int rr=-1; vector<int>f; for(auto w:tocy[1]) { if(incy[w]){rr=w;break;} f.push_back(w); } if(rr==-1) { for(auto w:cy[1]) { if(incy[w]){rr=w;break;} f.push_back(w); } } if(rr==-1) { for(auto w:tocy[1]) ans.push_back(w); for(auto w:cy[1])ans.push_back(w); reverse(tocy[1].begin(),tocy[1].end()); for(auto w:tocy[1])ans.push_back(w); reverse(tocy[1].begin(),tocy[1].end()); for(auto w:tocy[0])ans.push_back(w); reverse(cy[0].begin(),cy[0].end()); for(auto w:cy[0])ans.push_back(w); reverse(tocy[0].begin(),tocy[0].end()); for(auto w:tocy[0])ans.push_back(w); for(auto w:tocy[1])ans.push_back(w); reverse(cy[1].begin(),cy[1].end()); for(auto w:cy[1])ans.push_back(w); reverse(tocy[1].begin(),tocy[1].end()); for(auto w:tocy[1])ans.push_back(w); reverse(tocy[1].begin(),tocy[1].end()); reverse(gg.begin(),gg.end()); for(auto w:gg)ans.push_back(w); return ans; } for(auto w:f)ans.push_back(w); for(int i=0;i<cy[0].size();i++) { if(cy[0][i]!=rr)continue; for(int j=i-1;j>=0;j--)ans.push_back(cy[0][j]); for(int j=cy[0].size()-1;j>=i;j--)ans.push_back(cy[0][j]); reverse(f.begin(),f.end()); for(auto w:f)ans.push_back(w); reverse(gg.begin(),gg.end()); for(auto w:gg)ans.push_back(w); return ans; } }

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

islands.cpp: In function 'void dfs(int, int)':
islands.cpp:12:21: warning: comparison of constant '2' with boolean expression is always false [-Wbool-compare]
   12 |     if(fnd||(vsnd[x]==2))return;
      |              ~~~~~~~^~~
islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:158:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     for(int i=0;i<cy[0].size();i++)
      |                 ~^~~~~~~~~~~~~
islands.cpp:37:15: warning: control reaches end of non-void function [-Wreturn-type]
   37 |     queue<int>qq;
      |               ^~
#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...