Submission #959472

#	Time	Username	Problem	Language	Result	Execution time	Memory
959472		NemanjaSo2005	Split the Attractions (IOI19_split)	C++17	40 / 100	92 ms	24372 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;
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;
}
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++)
      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);
/*
	cout<<"STABLO"<<endl;
	for(int i=1;i<=N;i++){
      cout<<i<<": ";
      for(int x:stablo[i])
         cout<<x<<" ";
      cout<<endl;
	}*/

	dfs1(1,1);
	cent=findcentr(1,1);
	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);

     /* cout<<"ABC"<<endl;
      for(int x:A)
         cout<<x<<" ";
      cout<<endl;
      for(int x:B)
         cout<<x<<" ";
      cout<<endl;
      for(int x:C)
         cout<<x<<" ";
      cout<<endl;
*/
      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:61:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i=0;i<p.size();i++){
      |              ~^~~~~~~~~
split.cpp:126:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |       if(aa==B.size())
      |          ~~^~~~~~~~~~
split.cpp:128:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |       if(aa==C.size())
      |          ~~^~~~~~~~~~
split.cpp:130:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |       if(bb==C.size())
      |          ~~^~~~~~~~~~

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