oj.uz

Submission #959548

# Submission time Handle Problem Language Result Execution time Memory
959548 2024-04-08T12:29:34 Z NemanjaSo2005 Split the Attractions (IOI19_split) C++17
7 / 100
 2000 ms 27848 KB 
#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){
   prosli[gde]=true;
   for(int p:graf[gde])
      if(!prosli[p]){
         stablo[gde].push_back(p);
         stablo[p].push_back(gde);
         maketree(p);
      }
      else
         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;
      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){
   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)
         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);
      if(ima[r]>=a){
         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(a,b);
      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);
   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

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB ok, correct split
2 Correct 2 ms 6748 KB ok, correct split
3 Correct 1 ms 6748 KB ok, correct split
4 Correct 1 ms 6748 KB ok, correct split
5 Correct 2 ms 6748 KB ok, correct split
6 Correct 1 ms 6748 KB ok, correct split
7 Correct 72 ms 27372 KB ok, correct split
8 Correct 79 ms 24440 KB ok, correct split
9 Correct 67 ms 24008 KB ok, correct split
10 Correct 78 ms 27588 KB ok, correct split
11 Correct 69 ms 27848 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB ok, correct split
2 Correct 2 ms 6748 KB ok, correct split
3 Correct 2 ms 6748 KB ok, correct split
4 Correct 85 ms 24848 KB ok, correct split
5 Correct 98 ms 18884 KB ok, correct split
6 Correct 79 ms 27728 KB ok, correct split
7 Correct 70 ms 24680 KB ok, correct split
8 Execution timed out 2021 ms 24236 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB ok, correct split
2 Correct 89 ms 18676 KB ok, correct split
3 Correct 127 ms 11228 KB ok, correct split
4 Incorrect 1 ms 6748 KB invalid split: #1=9, #2=24, #3=33
5 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB ok, correct split
2 Incorrect 1 ms 6744 KB invalid split: #1=2, #2=1, #3=3
3 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB ok, correct split
2 Correct 2 ms 6748 KB ok, correct split
3 Correct 1 ms 6748 KB ok, correct split
4 Correct 1 ms 6748 KB ok, correct split
5 Correct 2 ms 6748 KB ok, correct split
6 Correct 1 ms 6748 KB ok, correct split
7 Correct 72 ms 27372 KB ok, correct split
8 Correct 79 ms 24440 KB ok, correct split
9 Correct 67 ms 24008 KB ok, correct split
10 Correct 78 ms 27588 KB ok, correct split
11 Correct 69 ms 27848 KB ok, correct split
12 Correct 2 ms 6748 KB ok, correct split
13 Correct 2 ms 6748 KB ok, correct split
14 Correct 2 ms 6748 KB ok, correct split
15 Correct 85 ms 24848 KB ok, correct split
16 Correct 98 ms 18884 KB ok, correct split
17 Correct 79 ms 27728 KB ok, correct split
18 Correct 70 ms 24680 KB ok, correct split
19 Execution timed out 2021 ms 24236 KB Time limit exceeded
20 Halted 0 ms 0 KB -