제출 #893540

#제출 시각아이디문제언어결과실행 시간메모리
893540MuhammadSaramSplit the Attractions (IOI19_split)C++17
100 / 100
89 ms23932 KiB
#include <bits/stdc++.h> using namespace std; const int M = 1e5; vector<int> nei[M],v, chi[M], ans; bool vis[M]; int col[3],subt[M],dep[M],mndep[M],cnt; void dfs(int u) { vis[u]=true; subt[u]=1; mndep[u]=dep[u]; for (int i:nei[u]) if (!vis[i]) { dep[i]=dep[u]+1; dfs(i); mndep[u]=min(mndep[u],mndep[i]); subt[u]+=subt[i]; chi[u].push_back(i); } else mndep[u]=min(mndep[u],dep[i]); } void dfs1(int u) { if (!cnt) return; vis[u]=true; ans[u]=col[1]; cnt--; for (int i:nei[u]) if (!vis[i]) dfs1(i); } vector<int> find_split(int n,int a,int b,int c,vector<int> p,vector<int> q) { for (int i=0;i<n;i++) ans.push_back(0); v={a,b,c}; sort(v.begin(),v.end()); for (int i=0;i<3;i++) { if (v[i]==a) { col[i]=1; a=-1; } else if(v[i]==b) { col[i]=2; b=-1; } else { col[i]=3; c=-1; } } a=v[0],b=v[1],c=v[2]; for (int i=0;i<p.size();i++) { nei[p[i]].push_back(q[i]); nei[q[i]].push_back(p[i]); } dfs(0); int u=0; while (1) { bool x=false; for (int i:chi[u]) if (subt[i]>=a) { u=i; x=true; break; } if (x) continue; for (int i=0;i<n;i++) vis[i]=(i==u); int fsize=1; for (int i:chi[u]) if (mndep[i]>=dep[u]) { fsize+=subt[i]; vis[i]=true; } for (int i=0;i<chi[u].size() and fsize<a;i++) if (mndep[chi[u][i]]<dep[u]) { fsize+=subt[chi[u][i]]; vis[chi[u][i]]=true; } if (fsize>=b and n-fsize>=a) swap(a,b),swap(col[0],col[1]); else if(n-fsize<b) break; queue<int> q; ans[u]=col[0]; for (int i:chi[u]) if (vis[i]) q.push(i); while (!q.empty() and cnt<a-1) { int x=q.front(); q.pop(); vis[x]=true; cnt++; ans[x]=col[0]; for (int i:chi[x]) q.push(i); } cnt=b; dfs1(0); for (int i=0;i<n;i++) if (!ans[i]) ans[i]=col[2]; break; } return ans; }

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

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  for (int i=0;i<p.size();i++)
      |               ~^~~~~~~~~
split.cpp:94:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for (int i=0;i<chi[u].size() and fsize<a;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...