Submission #959562

#	Time	Username	Problem	Language	Result	Execution time	Memory
959562		NemanjaSo2005	Split the Attractions (IOI19_split)	C++17	100 / 100	129 ms	28232 KiB

split

#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;
      if(x==cent or y==cent)
         continue;
      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;
}

Compilation message (stderr)

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

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 24 / 24
• Subtask 5: 36 / 36