Submission #830116

#	Time	Username	Problem	Language	Result	Execution time	Memory
830116		NemanjaSo2005	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	725 ms	15468 KiB

Joi

#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;
}

Ioi

#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 (stderr)

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 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17