제출 #907266

#제출 시각아이디문제언어결과실행 시간메모리
907266abcvuitunggio수천개의 섬 (IOI22_islands)C++17
34 / 100
48 ms24500 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,fun,res,ve; int n,m,ch[200001],pos[200001],deg[200001],x; 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 (true){ int i=adj[x][0]; int y=u[i]^v[i]^x; x=y; if (pos[i]!=-1){ x=i; break; } pos[i]=ve.size(); ve.push_back(i); } 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; int cnt=0; for (int i:b) cnt+=ch[i]; return (cnt==a.size()); } 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; } 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]) if (!--deg[u[i]^v[i]^x]) ve.push_back(u[i]^v[i]^x); ch[x]=1; x=y; break; } } } } void strain2(){ while (!ve.empty()){ int x=ve.back(); ve.pop_back(); ch[x]=1; for (int i:ke2[x]){ int y=u[i]^v[i]^x; if (!--deg[y]) ve.push_back(y); } } } variant <bool, vector <int>> find_journey(int N, int M, vector <int> U, vector <int> V) { n=N,m=M,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 (true){ int tmp=x; strain(); if (!deg[x]) return false; strain2(); if (ch[x]) return false; if (x==tmp) break; } for (int i=0;i<n;i++){ if (ch[i]) continue; 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]); if (check(c,c2)) fun=ve+c+rev(ve)+ve2+rev(c2)+rev(ve2); else fun=ve+c+rev(ve)+ve2+c2+rev(ve2)+ve+rev(c)+rev(ve)+ve2+rev(c2)+rev(ve2); return boring+fun+rev(boring); }

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

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