oj.uz

Submission #959556

# Submission time Handle Problem Language Result Execution time Memory
959556 2024-04-08T12:37:14 Z NemanjaSo2005 Split the Attractions (IOI19_split) C++17
18 / 100
 93 ms 26824 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 1 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 1 ms 6748 KB ok, correct split
5 Correct 2 ms 6748 KB ok, correct split
6 Correct 2 ms 6748 KB ok, correct split
7 Correct 79 ms 26308 KB ok, correct split
8 Correct 71 ms 23240 KB ok, correct split
9 Correct 75 ms 22728 KB ok, correct split
10 Correct 75 ms 26564 KB ok, correct split
11 Correct 86 ms 26824 KB ok, correct split

Subtask #2
11.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 1 ms 6748 KB ok, correct split
4 Correct 91 ms 23124 KB ok, correct split
5 Correct 66 ms 17640 KB ok, correct split
6 Correct 91 ms 26456 KB ok, correct split
7 Correct 74 ms 23492 KB ok, correct split
8 Correct 93 ms 22556 KB ok, correct split
9 Correct 65 ms 17608 KB ok, correct split
10 Correct 49 ms 18120 KB ok, correct split
11 Correct 47 ms 18204 KB ok, correct split
12 Correct 46 ms 18124 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB ok, correct split
2 Correct 58 ms 17608 KB ok, correct split
3 Correct 29 ms 10932 KB ok, correct split
4 Correct 2 ms 6744 KB ok, correct split
5 Correct 72 ms 20404 KB ok, correct split
6 Correct 68 ms 20132 KB ok, correct split
7 Correct 74 ms 19912 KB ok, correct split
8 Correct 63 ms 21524 KB ok, correct split
9 Correct 66 ms 19860 KB ok, correct split
10 Incorrect 23 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 7000 KB ok, correct split
2 Incorrect 2 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 1 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 1 ms 6748 KB ok, correct split
5 Correct 2 ms 6748 KB ok, correct split
6 Correct 2 ms 6748 KB ok, correct split
7 Correct 79 ms 26308 KB ok, correct split
8 Correct 71 ms 23240 KB ok, correct split
9 Correct 75 ms 22728 KB ok, correct split
10 Correct 75 ms 26564 KB ok, correct split
11 Correct 86 ms 26824 KB ok, correct split
12 Correct 2 ms 6748 KB ok, correct split
13 Correct 2 ms 6748 KB ok, correct split
14 Correct 1 ms 6748 KB ok, correct split
15 Correct 91 ms 23124 KB ok, correct split
16 Correct 66 ms 17640 KB ok, correct split
17 Correct 91 ms 26456 KB ok, correct split
18 Correct 74 ms 23492 KB ok, correct split
19 Correct 93 ms 22556 KB ok, correct split
20 Correct 65 ms 17608 KB ok, correct split
21 Correct 49 ms 18120 KB ok, correct split
22 Correct 47 ms 18204 KB ok, correct split
23 Correct 46 ms 18124 KB ok, correct split
24 Correct 1 ms 6744 KB ok, correct split
25 Correct 58 ms 17608 KB ok, correct split
26 Correct 29 ms 10932 KB ok, correct split
27 Correct 2 ms 6744 KB ok, correct split
28 Correct 72 ms 20404 KB ok, correct split
29 Correct 68 ms 20132 KB ok, correct split
30 Correct 74 ms 19912 KB ok, correct split
31 Correct 63 ms 21524 KB ok, correct split
32 Correct 66 ms 19860 KB ok, correct split
33 Incorrect 23 ms 10192 KB invalid split: #1=11111, #2=37, #3=22185
34 Halted 0 ms 0 KB -