제출 #422751

#제출 시각아이디문제언어결과실행 시간메모리
422751oleh1421Split the Attractions (IOI19_split)C++17
40 / 100
158 ms29716 KiB
//#include "grader.cpp" #include "split.h" #include <bits/stdc++.h> typedef long long ll; using namespace std; const int N=200010; vector<int>g[N],t[N]; pair<int,int>gr[3]; int sz[N]; int P[N]; bool used[N]; int timer=0; int tin[N],fup[N]; void dfs(int v,int pr){ sz[v]=1; tin[v]=fup[v]=++timer; P[v]=pr; used[v]=true; for (int to:g[v]){ if (!used[to]){ t[v].push_back(to); t[to].push_back(v); dfs(to,v); sz[v]+=sz[to]; fup[v]=min(fup[v],fup[to]); } else if (to!=pr) fup[v]=min(fup[v],tin[to]); } } int ans[N]; bool allowed[N]; void Mark(int v,int ind){ if (!gr[ind].first) return; gr[ind].first--; ans[v]=gr[ind].second; // if (!ind) cout<<"OK "<<v<<" "<<gr[ind].first<<" "<<gr[ind].second<<endl; for (int to:t[v]){ if (ans[to]) continue; Mark(to,ind); } } void dfs1(int v,int pr){ allowed[v]=true; for (int to:t[v]){ if (to!=pr){ dfs1(to,v); } } } void Mark1(int v,int ind){ if (!gr[ind].first) return; gr[ind].first--; ans[v]=gr[ind].second; // if (!ind) cout<<"OK "<<v<<" "<<gr[ind].first<<" "<<gr[ind].second<<endl; for (int to:g[v]){ if (ans[to] || !allowed[to]) continue; Mark1(to,ind); } } bool DONE=false; vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { gr[0]={a,1}; gr[1]={b,2}; gr[2]={c,3}; sort(gr,gr+3); for (int i=0;i<p.size();i++){ g[p[i]].push_back(q[i]); g[q[i]].push_back(p[i]); } dfs(0,-1); for (int i=0;i<n;i++) allowed[i]=true; for (int i=0;i<n;i++){ if (sz[i]>=gr[0].first && sz[i]<=n-gr[0].first){ if (sz[i]<=n-gr[1].first){ ans[P[i]]=gr[1].second; ans[i]=gr[0].second; Mark(P[i],1); Mark(i,0); } else { ans[P[i]]=gr[0].first; ans[i]=gr[1].first; Mark(P[i],0); Mark(i,1); } DONE=true; break; } } if (!DONE){ int V=-1; for (int i=0;i<n;i++){ if (sz[i]<=n-gr[0].first) continue; if (V==-1 || sz[i]<sz[V]) V=i; // if (sz[i]>=gr[0].first && sz[i]<=n-gr[0].first){ // if (sz[i]<=n-gr[1].first){ // ans[P[i]]=gr[1].second; // ans[i]=gr[0].second; // Mark(P[i],1); // Mark(i,0); // } else { // ans[P[i]]=gr[0].first; // ans[i]=gr[1].first; // Mark(P[i],0); // Mark(i,1); // } // DONE=true; // break; // } } for (int i=0;i<n;i++) allowed[i]=false; int cur=n-sz[V]; vector<int>u; for (int to:t[V]){ if (to==P[V]) continue; if (fup[to]<=tin[V]){ cur+=sz[to]; u.push_back(to); if (cur>=gr[0].first){ for (int i:u){ dfs1(i,V); } dfs1(P[V],V); Mark1(P[V],0); for (int i=0;i<n;i++) allowed[i]^=1; Mark1(V,1); DONE=true; break; } } } } // x<=a // n-x // dfs1(0,-1); if (DONE){ for (int i=0;i<n;i++){ if (!ans[i]) ans[i]=gr[2].second; } } vector<int>res; for (int i=0;i<n;i++) res.push_back(ans[i]); return res; } /** 9 9 3 3 3 0 1 0 2 2 3 2 4 2 5 2 6 2 7 2 8 8 0 9 10 4 2 3 0 1 0 2 0 3 0 4 0 6 0 8 1 7 3 7 4 5 5 6 */

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

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