Submission #959480

#	Time	Username	Problem	Language	Result	Execution time	Memory
959480		NemanjaSo2005	Split the Attractions (IOI19_split)	C++17	40 / 100	1863 ms	23604 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;
bool prosli[maxn],blok[maxn];
vector<int> graf[maxn],stablo[maxn],A,B,C,V,res;
mt19937_64 rng;
int perm[maxn];
void maketree(int gde){
   prosli[gde]=true;
   for(int p:graf[gde])
      if(!prosli[p]){
         stablo[gde].push_back(p);
         stablo[p].push_back(gde);
         maketree(p);
      }
}
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;
   //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;
      int v=collect(p,gde,kol);
      kol-=v;
      ret+=v;
      if(kol==0)
         return ret;
   }
   return ret;
}
void reset(){
   for(int i=1;i<=N;i++){
      siz[i]=0;
      prosli[i]=false;
      blok[i]=false;
      stablo[i].clear();
   }
   A.clear();
   B.clear();
   C.clear();
   V.clear();
}
vector<int> find_split(int n, int aa, int bb, int cc, vector<int> p, vector<int> q) {
   rng.seed(1525);
	N=n;
	for(int i=1;i<=N;i++)
      perm[i]=i;
   for(int i=2;i<=N;i++)
      swap(perm[i],perm[rng()%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);

   int maxit=N;
   if(N>2500)
      maxit=200;

   for(int it=1;it<=maxit;it++){
      int x=perm[it];
      //cout<<x<<endl;

      reset();

      maketree(x);
      dfs1(x,x);
      cent=findcentr(x,x);
      dfs1(cent,cent);
      int koji=-1;
      for(int x:stablo[cent])
         if(siz[x]>=a)
            koji=x;

      if(koji!=-1){
         blok[cent]=true;
         collect(koji,koji,a);
         A=V;
         V.clear();
         blok[cent]=false;
         blok[koji]=true;
         collect(cent,cent,b);
         B=V;

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

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