제출 #959561

#제출 시각아이디문제언어결과실행 시간메모리
959561NemanjaSo2005Split the Attractions (IOI19_split)C++17
40 / 100
85 ms25912 KiB
#include "split.h" #include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=1e5+5; ll N,a,b,c,siz[maxn],cent; int rod[maxn],vel[maxn],ima[maxn]; bool prosli[maxn],blok[maxn]; vector<int> graf[maxn],stablo[maxn],A,B,C,V,res; vector<pair<int,int>> ostale; void maketree(int gde,int pret){ prosli[gde]=true; for(int p:graf[gde]) if(!prosli[p]){ stablo[gde].push_back(p); stablo[p].push_back(gde); maketree(p,gde); } else if(p!=pret) ostale.push_back({p,gde}); } int dfs1(int gde,int pret){ siz[gde]=1; for(int p:stablo[gde]) if(p!=pret) siz[gde]+=dfs1(p,gde); return siz[gde]; } int findcentr(int gde,int pret){ for(int p:stablo[gde]){ if(p==pret) continue; if(siz[p]>=N/2+1) return findcentr(p,gde); } return gde; } int collect(int gde,int pret,int kol){ if(kol==0) return 0; if(prosli[gde]) return 0; prosli[gde]=true; //cout<<"COLLECT "<<gde<<" "<<kol<<endl; V.push_back(gde); int ret=1; kol--; for(int p:stablo[gde]){ if(p==pret) continue; if(blok[p]) continue; if(prosli[p]) continue; int v=collect(p,gde,kol); kol-=v; ret+=v; if(kol==0) return ret; } return ret; } int getpar(int x){ if(rod[x]==x) return x; rod[x]=getpar(rod[x]); return rod[x]; } int spoj(int a,int b){ // cout<<"SPOJ "<<a<<" "<<b<<endl; a=getpar(a); b=getpar(b); if(a==b) return a; if(vel[a]>vel[b]){ ima[a]+=ima[b]; rod[b]=a; return a; } else{ ima[b]+=ima[a]; rod[a]=b; vel[b]=max(vel[b],vel[a]+1); return b; } } void sveujedan(int gde,int pret){ spoj(gde,pret); for(int p:stablo[gde]) if(p!=pret and p!=cent) sveujedan(p,gde); } void resavaj(){ for(int x:stablo[cent]) sveujedan(x,x); for(int i=1;i<=N;i++) prosli[i]=false; for(int x:stablo[cent]){ int r=getpar(x); //cout<<r<<" "<<ima[r]<<endl; if(ima[r]>=a){ // cout<<"OVDE"<<endl; blok[cent]=true; collect(r,r,a); A=V; blok[cent]=false; for(int x:V) blok[x]=true; V.clear(); collect(cent,cent,b); B=V; return; } } for(auto e:ostale){ int x=e.first; int y=e.second; int z=spoj(x,y); stablo[x].push_back(y); stablo[y].push_back(x); if(ima[z]>=b){ blok[cent]=true; collect(z,z,b); B=V; blok[cent]=false; for(int x:V) blok[x]=true; V.clear(); collect(cent,cent,a); A=V; return; } if(ima[z]>=a){ blok[cent]=true; collect(z,z,a); A=V; blok[cent]=false; for(int x:V) blok[x]=true; V.clear(); collect(cent,cent,b); B=V; return; } } } vector<int> find_split(int n, int aa, int bb, int cc, vector<int> p, vector<int> q) { N=n; for(int i=1;i<=N;i++){ rod[i]=i; ima[i]=vel[i]=1; } for(int i=1;i<=N;i++) res.push_back(0); a=aa; b=bb; c=cc; for(int i=0;i<p.size();i++){ int x=p[i]; int y=q[i]; x++; y++; graf[x].push_back(y); graf[y].push_back(x); } if(a>b) swap(a,b); if(b>c) swap(b,c); if(a>b) swap(a,b); maketree(1,1); dfs1(1,1); cent=findcentr(1,1); dfs1(cent,cent); resavaj(); /// Procesira centroid if(A.size()!=0){ for(int i=1;i<=N;i++) prosli[i]=false; for(int x:A) prosli[x]=true; for(int x:B) prosli[x]=true; for(int i=1;i<=N;i++) if(prosli[i]==false) C.push_back(i); if(aa==B.size()) swap(A,B); if(aa==C.size()) swap(A,C); if(bb==C.size()) swap(B,C); for(int x:A) res[x-1]=1; for(int x:B) res[x-1]=2; for(int x:C) res[x-1]=3; return res; } return res; }

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

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:161:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |  for(int i=0;i<p.size();i++){
      |              ~^~~~~~~~~
split.cpp:193:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |       if(aa==B.size())
      |          ~~^~~~~~~~~~
split.cpp:195:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |       if(aa==C.size())
      |          ~~^~~~~~~~~~
split.cpp:197:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |       if(bb==C.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...