제출 #907397

#제출 시각아이디문제언어결과실행 시간메모리
907397abcvuitunggio수천개의 섬 (IOI22_islands)C++17
70.75 / 100
112 ms31376 KiB
#include "islands.h" #include <variant> #include <vector> #include <cstring> #include <algorithm> using namespace std; vector <int> u,v,ke[200001],ke2[200001],adj[200001],boring,res,ve; int ch[200001],pos[200001],deg[200001],x,C; void strain(){ while (deg[x]==1){ for (int i:ke[x]){ int y=u[i]^v[i]^x; if (!ch[y]){ boring.push_back(i); for (int i:ke2[x]){ int y=u[i]^v[i]^x; if (!ch[y]&&!--deg[y]) ve.push_back(y); } C=0; ch[x]=1; x=y; break; } } } } void strain2(){ while (!ve.empty()){ C=0; int x=ve.back(); ve.pop_back(); ch[x]=1; for (int i:ke2[x]){ int y=u[i]^v[i]^x; if (ch[y]) continue; if (!--deg[y]) ve.push_back(y); } } } pair <vector <int>, vector <int>> dfs(int s, int x){ vector <int> ve,cycle; memset(pos,-1,sizeof(pos)); ve.push_back(x); pos[x]=0; x=u[x]^v[x]^s; while (pos[adj[x][0]]==-1){ int i=adj[x][0]; int y=u[i]^v[i]^x; x=y; pos[i]=ve.size(); ve.push_back(i); } x=adj[x][0]; for (int i=pos[x];i<ve.size();i++) cycle.push_back(ve[i]); while (ve.size()>pos[x]) ve.pop_back(); return {ve,cycle}; } bool check(vector <int> a, vector <int> b){ if (a.size()!=b.size()) return false; memset(ch,0,sizeof(ch)); for (int i:a) ch[i]=1; for (int i:b) if (!ch[i]) return true; return false; } vector <int> rev(vector <int> v){ reverse(v.begin(),v.end()); return v; } vector <int> operator +(vector <int> a, vector <int> b){ for (int i:b) a.push_back(i); return a; } variant <bool, vector <int>> find_journey(int n, int m, vector <int> U, vector <int> V) { u=U,v=V; for (int i=0;i<m;i++){ ke[u[i]].push_back(i); ke2[v[i]].push_back(i); deg[u[i]]++; } for (int i=0;i<n;i++) if (!deg[i]) ve.push_back(i); while (!C){ C=1; strain(); strain2(); } if (ch[x]) return false; for (int i=0;i<n;i++) for (int j:ke[i]) if (!ch[u[j]^v[j]^i]) adj[i].push_back(j); auto [ve,c]=dfs(x,adj[x][0]); auto [ve2,c2]=dfs(x,adj[x][1]); res=boring+ve+c+rev(ve)+ve2; if (check(c,c2)) res=res+c2+rev(ve2)+ve+rev(ve+c)+ve2; return res+rev(boring+ve2+c2); }

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

islands.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > dfs(int, int)':
islands.cpp:57:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i=pos[x];i<ve.size();i++)
      |                       ~^~~~~~~~~~
islands.cpp:59:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |     while (ve.size()>pos[x])
      |            ~~~~~~~~~^~~~~~~
#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...