oj.uz

Submission #830116

# Submission time Handle Problem Language Result Execution time Memory
830116 2023-08-18T19:03:50 Z NemanjaSo2005 Amusement Park (JOI17_amusement_park) C++17
100 / 100
 725 ms 15468 KB 
#include<bits/stdc++.h>
#define ll long long
#include "Joi.h"
#include "Ioi.h"
using namespace std;
int rod[10005],vel[10005],koji[10005],ostalo;
ll step[65];
bool orgst[10005],koristi[10005];
int N,K=60;
vector<int> stablo[10005],S,ubacen[10005];
int getp(int x){
   if(rod[x]==x)
      return x;
   rod[x]=getp(rod[x]);
   return rod[x];
}
bool spoj(int a,int b){
   a=getp(a);
   b=getp(b);
   if(a==b)
      return false;
   if(vel[a]>vel[b])
      rod[b]=a;
   else{
      rod[a]=b;
      vel[b]=max(vel[a]+1,vel[b]);
   }
   return true;
}
void dfs(int gde,int pret){
   if(ostalo==0)
      return;
   //cout<<gde<<" "<<ostalo<<endl;
   S.push_back(gde);
   ostalo--;
   koji[gde]=ostalo;
   for(int i=0;i<stablo[gde].size();i++)
      if(stablo[gde][i]!=pret)
         dfs(stablo[gde][i],gde);
   return;
}
pair<int,int> najdalji(int gde,int pret,bool ex=false){
   if(koristi[gde]==false and ex==false)
      return {gde,0};
   int d=0;
   pair<int,int> ret={gde,1},pp;
   for(int i=0;i<stablo[gde].size();i++){
      if(stablo[gde][i]==pret)
         continue;
      pp=najdalji(stablo[gde][i],gde);
      if(pp.second>d){
         d=pp.second;
         ret=pp;
         ret.second++;
      }
   }
   return ret;
}
void dfs2(int gde,int pret,vector<int> ust){
   if(orgst[gde])
      return;
   for(int i=0;i<ust.size();i++)
      koristi[ust[i]]=true;
   pair<int,int> pp =najdalji(gde,gde,true);
   int najd=pp.first;
  // cout<<gde<<" "<<pret<<" najdalji "<<najd<<endl;
   for(int i=0;i<ust.size();i++)
      if(ust[i]==najd){
         swap(ust[i],ust[ust.size()-1]);
         ust.pop_back();
         break;
      }
   ust.push_back(gde);
   ubacen[gde]=ust;

   koji[gde]=koji[najd];
   koristi[najd]=false;
   for(int i=0;i<ust.size();i++)
      koristi[ust[i]]=false;
   for(int i=0;i<stablo[gde].size();i++)
      if(stablo[gde][i]!=pret)
         dfs2(stablo[gde][i],gde,ust);
}
void init(int n,int M,int A[],int B[]){
   N=n;
   for(int i=0;i<N;i++){
      stablo[i].clear();
      ubacen[i].clear();
      koristi[i]=0;
      orgst[i]=0;
      koji[i]=0;
      rod[i]=i;
      vel[i]=0;
   }
   for(int i=0;i<M;i++){
      if(!spoj(A[i],B[i]))
         continue;
      stablo[A[i]].push_back(B[i]);
      stablo[B[i]].push_back(A[i]);
   }
   /*cout<<"STABLO: "<<endl;
   for(int i=0;i<N;i++){
      cout<<i<<": ";
      for(int j=0;j<stablo[i].size();j++)
         cout<<stablo[i][j]<<" ";
      cout<<endl;
   }*/

   ostalo=K;
   dfs(0,0);
   for(int i=0;i<S.size();i++){
      orgst[S[i]]=true;
      ubacen[S[i]]=S;
   }
   for(int i=0;i<S.size();i++){
      for(int j=0;j<stablo[S[i]].size();j++)
         dfs2(stablo[S[i]][j],S[i],S);
   }
  // for(int i=0;i<N;i++)
  //    cout<<i<<": "<<koji[i]<<endl;
  // cout<<endl;
   step[0]=1;
   for(int i=1;i<=59;i++)
      step[i]=step[i-1]<<1;
}
void Joi(int n, int M, int A[], int B[], long long X, int T) {
   init(n,M,A,B);
   for(int i=0;i<N;i++)
      MessageBoard(i,(step[koji[i]]&X)!=0);
   return;
}
#include<bits/stdc++.h>
#define ll long long
#include "Joi.h"
#include "Ioi.h"
using namespace std;
int rod[10005],vel[10005],koji[10005],ostalo;
ll step[65];
bool orgst[10005],koristi[10005];
int N,K=60;
vector<int> stablo[10005],S,ubacen[10005];
int getp(int x){
   if(rod[x]==x)
      return x;
   rod[x]=getp(rod[x]);
   return rod[x];
}
bool spoj(int a,int b){
   a=getp(a);
   b=getp(b);
   if(a==b)
      return false;
   if(vel[a]>vel[b])
      rod[b]=a;
   else{
      rod[a]=b;
      vel[b]=max(vel[a]+1,vel[b]);
   }
   return true;
}
void dfs(int gde,int pret){
   if(ostalo==0)
      return;
   //cout<<gde<<" "<<ostalo<<endl;
   S.push_back(gde);
   ostalo--;
   koji[gde]=ostalo;
   for(int i=0;i<stablo[gde].size();i++)
      if(stablo[gde][i]!=pret)
         dfs(stablo[gde][i],gde);
   return;
}
pair<int,int> najdalji(int gde,int pret,bool ex=false){
   if(koristi[gde]==false and ex==false)
      return {gde,0};
   int d=0;
   pair<int,int> ret={gde,1},pp;
   for(int i=0;i<stablo[gde].size();i++){
      if(stablo[gde][i]==pret)
         continue;
      pp=najdalji(stablo[gde][i],gde);
      if(pp.second>d){
         d=pp.second;
         ret=pp;
         ret.second++;
      }
   }
   return ret;
}
void dfs2(int gde,int pret,vector<int> ust){
   if(orgst[gde])
      return;
   for(int i=0;i<ust.size();i++)
      koristi[ust[i]]=true;
   pair<int,int> pp =najdalji(gde,gde,true);
   int najd=pp.first;
  // cout<<gde<<" "<<pret<<" najdalji "<<najd<<endl;
   for(int i=0;i<ust.size();i++)
      if(ust[i]==najd){
         swap(ust[i],ust[ust.size()-1]);
         ust.pop_back();
         break;
      }
   ust.push_back(gde);
   ubacen[gde]=ust;

   koji[gde]=koji[najd];
   koristi[najd]=false;
   for(int i=0;i<ust.size();i++)
      koristi[ust[i]]=false;
   for(int i=0;i<stablo[gde].size();i++)
      if(stablo[gde][i]!=pret)
         dfs2(stablo[gde][i],gde,ust);
}
void init(int n,int M,int A[],int B[]){
   N=n;
   for(int i=0;i<N;i++){
      stablo[i].clear();
      ubacen[i].clear();
      koristi[i]=0;
      orgst[i]=0;
      koji[i]=0;
      rod[i]=i;
      vel[i]=0;
   }
   for(int i=0;i<M;i++){
      if(!spoj(A[i],B[i]))
         continue;
      stablo[A[i]].push_back(B[i]);
      stablo[B[i]].push_back(A[i]);
   }
   /*cout<<"STABLO: "<<endl;
   for(int i=0;i<N;i++){
      cout<<i<<": ";
      for(int j=0;j<stablo[i].size();j++)
         cout<<stablo[i][j]<<" ";
      cout<<endl;
   }*/

   ostalo=K;
   dfs(0,0);
   for(int i=0;i<S.size();i++){
      orgst[S[i]]=true;
      ubacen[S[i]]=S;
   }
   for(int i=0;i<S.size();i++){
      for(int j=0;j<stablo[S[i]].size();j++)
         dfs2(stablo[S[i]][j],S[i],S);
   }
  // for(int i=0;i<N;i++)
  //    cout<<i<<": "<<koji[i]<<endl;
  // cout<<endl;
   step[0]=1;
   for(int i=1;i<=59;i++)
      step[i]=step[i-1]<<1;
}
int broj[10005];
int poz;
void dfs3(int gde,int pret){
   if(!koristi[gde])
      return;
   //cout<<gde<<" "<<pret<<endl;
   if(poz!=gde){
      broj[gde]=Move(gde);
      poz=gde;
   }
   for(int i=0;i<stablo[gde].size();i++){
      if(stablo[gde][i]!=pret){
      //   cout<<"IDI U "<<stablo[gde][i]<<" IZ "<<gde<<endl;
         dfs3(stablo[gde][i],gde);
      }
      if(poz!=gde){
         broj[gde]=Move(gde);
         poz=gde;
      }
   }
   return;
}
long long Ioi(int n, int M, int A[], int B[], int P, int V, int T) {
   init(n,M,A,B);
   broj[P]=V;
   poz=P;
   for(int i=0;i<ubacen[P].size();i++)
      koristi[ubacen[P][i]]=true;
   dfs3(P,P);
   ll res=0;
  /* for(int i=0;i<N;i++)
      cout<<i<<" stoji "<<broj[i]<<endl;
   for(int i=0;i<ubacen[P].size();i++)
      cout<<ubacen[P][i]<<" ";
   cout<<endl;*/
   for(int i=0;i<ubacen[P].size();i++){
      res+=broj[ubacen[P][i]]*step[koji[ubacen[P][i]]];
      //cout<<ubacen[P][i]<<" "<<res<<endl;
   }
   return res;
}

Compilation message

Joi.cpp: In function 'void dfs(int, int)':
Joi.cpp:37:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    for(int i=0;i<stablo[gde].size();i++)
      |                ~^~~~~~~~~~~~~~~~~~~
Joi.cpp: In function 'std::pair<int, int> najdalji(int, int, bool)':
Joi.cpp:47:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |    for(int i=0;i<stablo[gde].size();i++){
      |                ~^~~~~~~~~~~~~~~~~~~
Joi.cpp: In function 'void dfs2(int, int, std::vector<int>)':
Joi.cpp:62:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |    for(int i=0;i<ust.size();i++)
      |                ~^~~~~~~~~~~
Joi.cpp:67:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    for(int i=0;i<ust.size();i++)
      |                ~^~~~~~~~~~~
Joi.cpp:78:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |    for(int i=0;i<ust.size();i++)
      |                ~^~~~~~~~~~~
Joi.cpp:80:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |    for(int i=0;i<stablo[gde].size();i++)
      |                ~^~~~~~~~~~~~~~~~~~~
Joi.cpp: In function 'void init(int, int, int*, int*)':
Joi.cpp:111:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |    for(int i=0;i<S.size();i++){
      |                ~^~~~~~~~~
Joi.cpp:115:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |    for(int i=0;i<S.size();i++){
      |                ~^~~~~~~~~
Joi.cpp:116:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |       for(int j=0;j<stablo[S[i]].size();j++)
      |                   ~^~~~~~~~~~~~~~~~~~~~

Ioi.cpp: In function 'void dfs(int, int)':
Ioi.cpp:37:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    for(int i=0;i<stablo[gde].size();i++)
      |                ~^~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'std::pair<int, int> najdalji(int, int, bool)':
Ioi.cpp:47:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |    for(int i=0;i<stablo[gde].size();i++){
      |                ~^~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfs2(int, int, std::vector<int>)':
Ioi.cpp:62:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |    for(int i=0;i<ust.size();i++)
      |                ~^~~~~~~~~~~
Ioi.cpp:67:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    for(int i=0;i<ust.size();i++)
      |                ~^~~~~~~~~~~
Ioi.cpp:78:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |    for(int i=0;i<ust.size();i++)
      |                ~^~~~~~~~~~~
Ioi.cpp:80:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |    for(int i=0;i<stablo[gde].size();i++)
      |                ~^~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void init(int, int, int*, int*)':
Ioi.cpp:111:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |    for(int i=0;i<S.size();i++){
      |                ~^~~~~~~~~
Ioi.cpp:115:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |    for(int i=0;i<S.size();i++){
      |                ~^~~~~~~~~
Ioi.cpp:116:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |       for(int j=0;j<stablo[S[i]].size();j++)
      |                   ~^~~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfs3(int, int)':
Ioi.cpp:136:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |    for(int i=0;i<stablo[gde].size();i++){
      |                ~^~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:152:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |    for(int i=0;i<ubacen[P].size();i++)
      |                ~^~~~~~~~~~~~~~~~~
Ioi.cpp:161:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |    for(int i=0;i<ubacen[P].size();i++){
      |                ~^~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1548 KB Output is correct
2 Correct 2 ms 1796 KB Output is correct
3 Correct 2 ms 1800 KB Output is correct
4 Correct 1 ms 1796 KB Output is correct
5 Correct 2 ms 1804 KB Output is correct
6 Correct 2 ms 1792 KB Output is correct
7 Correct 3 ms 1808 KB Output is correct
8 Correct 2 ms 1808 KB Output is correct
9 Correct 2 ms 1736 KB Output is correct
10 Correct 2 ms 1804 KB Output is correct
11 Correct 4 ms 1996 KB Output is correct
12 Correct 2 ms 1540 KB Output is correct
13 Correct 2 ms 1808 KB Output is correct
14 Correct 3 ms 1808 KB Output is correct
15 Correct 2 ms 1864 KB Output is correct
16 Correct 2 ms 1808 KB Output is correct
17 Correct 2 ms 1808 KB Output is correct
18 Correct 2 ms 1792 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 9176 KB Output is correct
2 Correct 47 ms 9164 KB Output is correct
3 Correct 38 ms 9216 KB Output is correct
4 Correct 30 ms 8504 KB Output is correct
5 Correct 34 ms 11568 KB Output is correct
6 Correct 36 ms 10304 KB Output is correct
7 Correct 35 ms 9588 KB Output is correct
8 Correct 40 ms 10236 KB Output is correct
9 Correct 43 ms 9864 KB Output is correct
10 Correct 521 ms 8484 KB Output is correct
11 Correct 571 ms 8432 KB Output is correct
12 Correct 27 ms 7936 KB Output is correct
13 Correct 26 ms 7876 KB Output is correct
14 Correct 32 ms 8012 KB Output is correct
15 Correct 89 ms 8472 KB Output is correct
16 Correct 82 ms 8408 KB Output is correct
17 Correct 44 ms 8400 KB Output is correct
18 Correct 33 ms 8440 KB Output is correct
19 Correct 32 ms 8452 KB Output is correct
20 Correct 27 ms 12056 KB Output is correct
21 Correct 27 ms 11832 KB Output is correct
22 Correct 36 ms 9632 KB Output is correct
23 Correct 37 ms 9660 KB Output is correct
24 Correct 36 ms 9436 KB Output is correct
25 Correct 44 ms 9580 KB Output is correct
26 Correct 36 ms 10352 KB Output is correct
27 Correct 44 ms 10224 KB Output is correct
28 Correct 35 ms 10416 KB Output is correct
29 Correct 40 ms 8920 KB Output is correct
30 Correct 44 ms 9212 KB Output is correct
31 Correct 2 ms 1804 KB Output is correct
32 Correct 2 ms 1792 KB Output is correct
33 Correct 2 ms 1812 KB Output is correct
34 Correct 2 ms 1792 KB Output is correct
35 Correct 2 ms 1736 KB Output is correct
36 Correct 1 ms 1540 KB Output is correct
37 Correct 2 ms 1548 KB Output is correct
38 Correct 2 ms 1540 KB Output is correct
39 Correct 2 ms 1548 KB Output is correct
40 Correct 2 ms 1784 KB Output is correct
41 Correct 2 ms 1732 KB Output is correct
42 Correct 2 ms 1540 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1804 KB Output is correct
2 Correct 2 ms 1796 KB Output is correct
3 Correct 2 ms 1800 KB Output is correct
4 Correct 5 ms 3884 KB Output is correct
5 Correct 5 ms 3896 KB Output is correct
6 Correct 5 ms 3884 KB Output is correct
7 Correct 5 ms 3888 KB Output is correct
8 Correct 5 ms 3892 KB Output is correct
9 Correct 27 ms 15468 KB Output is correct
10 Correct 31 ms 15388 KB Output is correct
11 Correct 27 ms 15320 KB Output is correct
12 Correct 2 ms 1604 KB Output is correct
13 Correct 1 ms 1540 KB Output is correct
14 Correct 1 ms 1596 KB Output is correct
15 Correct 1 ms 1540 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 9264 KB Output is correct
2 Correct 51 ms 9232 KB Output is correct
3 Correct 49 ms 9124 KB Output is correct
4 Correct 30 ms 8456 KB Output is correct
5 Correct 43 ms 12360 KB Output is correct
6 Correct 44 ms 9936 KB Output is correct
7 Correct 35 ms 9236 KB Output is correct
8 Correct 40 ms 9184 KB Output is correct
9 Correct 36 ms 9156 KB Output is correct
10 Correct 725 ms 8448 KB Output is correct
11 Correct 524 ms 8480 KB Output is correct
12 Correct 26 ms 7960 KB Output is correct
13 Correct 28 ms 7832 KB Output is correct
14 Correct 27 ms 8228 KB Output is correct
15 Correct 78 ms 8400 KB Output is correct
16 Correct 82 ms 8344 KB Output is correct
17 Correct 35 ms 8356 KB Output is correct
18 Correct 41 ms 8440 KB Output is correct
19 Correct 35 ms 8468 KB Output is correct
20 Correct 27 ms 12124 KB Output is correct
21 Correct 31 ms 11728 KB Output is correct
22 Correct 44 ms 9512 KB Output is correct
23 Correct 39 ms 9956 KB Output is correct
24 Correct 36 ms 9928 KB Output is correct
25 Correct 37 ms 10384 KB Output is correct
26 Correct 39 ms 10216 KB Output is correct
27 Correct 38 ms 10516 KB Output is correct
28 Correct 38 ms 9612 KB Output is correct
29 Correct 32 ms 8944 KB Output is correct
30 Correct 43 ms 9792 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 9188 KB Output is correct
2 Correct 46 ms 9132 KB Output is correct
3 Correct 46 ms 9164 KB Output is correct
4 Correct 32 ms 8532 KB Output is correct
5 Correct 36 ms 13728 KB Output is correct
6 Correct 48 ms 10184 KB Output is correct
7 Correct 36 ms 9120 KB Output is correct
8 Correct 35 ms 9752 KB Output is correct
9 Correct 36 ms 9176 KB Output is correct
10 Correct 524 ms 8472 KB Output is correct
11 Correct 527 ms 8408 KB Output is correct
12 Correct 25 ms 7872 KB Output is correct
13 Correct 26 ms 7944 KB Output is correct
14 Correct 27 ms 8188 KB Output is correct
15 Correct 70 ms 8364 KB Output is correct
16 Correct 80 ms 8408 KB Output is correct
17 Correct 32 ms 8456 KB Output is correct
18 Correct 33 ms 8332 KB Output is correct
19 Correct 33 ms 8544 KB Output is correct
20 Correct 28 ms 11972 KB Output is correct
21 Correct 27 ms 11748 KB Output is correct
22 Correct 41 ms 9628 KB Output is correct
23 Correct 37 ms 9660 KB Output is correct
24 Correct 35 ms 9536 KB Output is correct
25 Correct 36 ms 9432 KB Output is correct
26 Correct 35 ms 9516 KB Output is correct
27 Correct 35 ms 10316 KB Output is correct
28 Correct 35 ms 10776 KB Output is correct
29 Correct 32 ms 9764 KB Output is correct
30 Correct 33 ms 10008 KB Output is correct
31 Correct 2 ms 1796 KB Output is correct
32 Correct 2 ms 1804 KB Output is correct
33 Correct 2 ms 1804 KB Output is correct
34 Correct 2 ms 1760 KB Output is correct
35 Correct 2 ms 1796 KB Output is correct
36 Correct 1 ms 1728 KB Output is correct
37 Correct 1 ms 1540 KB Output is correct
38 Correct 1 ms 1600 KB Output is correct
39 Correct 1 ms 1540 KB Output is correct
40 Correct 2 ms 1804 KB Output is correct
41 Correct 2 ms 1804 KB Output is correct
42 Correct 1 ms 1544 KB Output is correct