oj.uz

Submission #959558

# Submission time Handle Problem Language Result Execution time Memory
959558 2024-04-08T12:38:36 Z NemanjaSo2005 Split the Attractions (IOI19_split) C++17
18 / 100
 95 ms 26820 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;
      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);
   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:160:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |  for(int i=0;i<p.size();i++){
      |              ~^~~~~~~~~
split.cpp:192:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |       if(aa==B.size())
      |          ~~^~~~~~~~~~
split.cpp:194:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |       if(aa==C.size())
      |          ~~^~~~~~~~~~
split.cpp:196:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |       if(bb==C.size())
      |          ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB ok, correct split
2 Correct 1 ms 6748 KB ok, correct split
3 Correct 3 ms 6748 KB ok, correct split
4 Correct 1 ms 6748 KB ok, correct split
5 Correct 1 ms 6748 KB ok, correct split
6 Correct 2 ms 6748 KB ok, correct split
7 Correct 82 ms 26288 KB ok, correct split
8 Correct 66 ms 23232 KB ok, correct split
9 Correct 73 ms 22736 KB ok, correct split
10 Correct 85 ms 26360 KB ok, correct split
11 Correct 70 ms 26820 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB ok, correct split
2 Correct 1 ms 6748 KB ok, correct split
3 Correct 2 ms 6748 KB ok, correct split
4 Correct 78 ms 23216 KB ok, correct split
5 Correct 75 ms 17528 KB ok, correct split
6 Correct 89 ms 26552 KB ok, correct split
7 Correct 68 ms 23500 KB ok, correct split
8 Correct 95 ms 22348 KB ok, correct split
9 Correct 65 ms 17604 KB ok, correct split
10 Correct 50 ms 18124 KB ok, correct split
11 Correct 49 ms 18116 KB ok, correct split
12 Correct 46 ms 18196 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB ok, correct split
2 Correct 75 ms 17528 KB ok, correct split
3 Correct 22 ms 10708 KB ok, correct split
4 Correct 1 ms 7000 KB ok, correct split
5 Correct 74 ms 20524 KB ok, correct split
6 Correct 91 ms 20168 KB ok, correct split
7 Correct 62 ms 20116 KB ok, correct split
8 Correct 63 ms 21444 KB ok, correct split
9 Correct 67 ms 19652 KB ok, correct split
10 Incorrect 19 ms 10192 KB invalid split: #1=11111, #2=37, #3=22185
11 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB ok, correct split
2 Incorrect 1 ms 6748 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 6748 KB ok, correct split
2 Correct 1 ms 6748 KB ok, correct split
3 Correct 3 ms 6748 KB ok, correct split
4 Correct 1 ms 6748 KB ok, correct split
5 Correct 1 ms 6748 KB ok, correct split
6 Correct 2 ms 6748 KB ok, correct split
7 Correct 82 ms 26288 KB ok, correct split
8 Correct 66 ms 23232 KB ok, correct split
9 Correct 73 ms 22736 KB ok, correct split
10 Correct 85 ms 26360 KB ok, correct split
11 Correct 70 ms 26820 KB ok, correct split
12 Correct 1 ms 6748 KB ok, correct split
13 Correct 1 ms 6748 KB ok, correct split
14 Correct 2 ms 6748 KB ok, correct split
15 Correct 78 ms 23216 KB ok, correct split
16 Correct 75 ms 17528 KB ok, correct split
17 Correct 89 ms 26552 KB ok, correct split
18 Correct 68 ms 23500 KB ok, correct split
19 Correct 95 ms 22348 KB ok, correct split
20 Correct 65 ms 17604 KB ok, correct split
21 Correct 50 ms 18124 KB ok, correct split
22 Correct 49 ms 18116 KB ok, correct split
23 Correct 46 ms 18196 KB ok, correct split
24 Correct 1 ms 6748 KB ok, correct split
25 Correct 75 ms 17528 KB ok, correct split
26 Correct 22 ms 10708 KB ok, correct split
27 Correct 1 ms 7000 KB ok, correct split
28 Correct 74 ms 20524 KB ok, correct split
29 Correct 91 ms 20168 KB ok, correct split
30 Correct 62 ms 20116 KB ok, correct split
31 Correct 63 ms 21444 KB ok, correct split
32 Correct 67 ms 19652 KB ok, correct split
33 Incorrect 19 ms 10192 KB invalid split: #1=11111, #2=37, #3=22185
34 Halted 0 ms 0 KB -