Submission #906728

#	Time	Username	Problem	Language	Result	Execution time	Memory
906728		NemanjaSo2005	Fun Tour (APIO20_fun)	C++17	100 / 100	194 ms	21196 KiB

fun

#include "fun.h"
int N;
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int root,depth[maxn];
int odakle;
vector<int> R,koji[5];
vector<int> V;
bool podub(int a,int b){
   return depth[a]<depth[b];
}
void findroot(){
   root=1;
   for(int i=2;i<=N;i++)
      if(attractionsBehind(root-1,i-1)>=(N)/2+1)
         root=i;
   return;
}
void finddepth(){
   for(int i=1;i<=N;i++){
      depth[i]=hoursRequired(root-1,i-1);
    //  cout<<i<<" dubina "<<depth[i]<<endl;
      if(depth[i]==1)
         R.push_back(i);
   }
   return;
}
bool insubtree(int a,int b){
   //cout<<a<<" "<<b<<" "<<attractionsBehind(a-1,b-1)<<endl;
   return attractionsBehind(a-1,b-1)>=(N)/2+1;
}
void findsubtree(){
   for(int i=1;i<=N;i++){
      if(depth[i]==0)
         continue;
      if(insubtree(i,R[0]))
         koji[0].push_back(i);
      else if(insubtree(i,R[1]))
         koji[1].push_back(i);
      else
         koji[2].push_back(i);
   }
}
int dist(int a,int b){
   return depth[a]+depth[b];
}
void dodaj(int idx){
   if(koji[idx].size()==0)
      return;
   odakle=idx;
   //cout<<idx<<" "<<koji[idx].back()<<endl;
   V.push_back(koji[idx].back());
   koji[idx].pop_back();
   //cout<<"DODAJEM "<<idx<<" "<<depth[V.back()]<<endl;
   return;
}
void spoj(int a,int b){
   //cout<<"SPAJAM "<<a<<" "<<b<<endl;
   //cout<<V.size()<<" "<<odakle<<endl;
   if(a>b)
      swap(a,b);
   int c=a^b^3;
 
   if(odakle!=c)
      if(dist(V.back(),koji[c].back())<dist(koji[c].back(),koji[3^c^odakle].back()))
         dodaj(3^odakle^c);
 
   for(int i=0;i<koji[b].size();i++)
      koji[a].push_back(koji[b][i]);
 
   sort(koji[a].begin(),koji[a].end(),podub);
   if(odakle==b)
      odakle=a;
   if(b==1){
      koji[1]=koji[2];
      if(odakle==2)
         odakle=1;
   }
   koji[2].clear();
 
   //cout<<odakle<<endl;
   //cout<<V.size()<<endl;
}
vector<int> createFunTour(int n, int Q) {
   N=n;
   findroot();
   finddepth();
   findsubtree();
   for(int i=0;i<=2;i++)
      if(koji[i].size())
         sort(koji[i].begin(),koji[i].end(),podub);
   if(koji[2].size()){
      if(depth[koji[0].back()]>=depth[koji[1].back()] and depth[koji[0].back()]>=depth[koji[2].back()])
         dodaj(0);
      else if(depth[koji[1].back()]>=depth[koji[0].back()] and depth[koji[1].back()]>=depth[koji[2].back()])
         dodaj(1);
      else
         dodaj(2);
   }
   else
      if(koji[1].size()>koji[0].size())
         dodaj(1);
      else
         dodaj(0);
 
   while(koji[2].size()){

      if(koji[0].size()+koji[1].size()<=koji[2].size()){
         spoj(0,1);
         break;
      }
      if(koji[0].size()+koji[2].size()<=koji[1].size()){
         spoj(0,2);
         break;
      }
      if(koji[1].size()+koji[2].size()<=koji[0].size()){
         spoj(1,2);
         break;
      }
      int nd=0;
      if(odakle==0)
         nd=1;
      for(int i=1;i<=2;i++)
         if(depth[koji[i].back()]>depth[koji[nd].back()] and i!=odakle)
            nd=i;
      dodaj(nd);
   }
  // cout<<"BBB"<<endl;
   //cout<<odakle<<endl;
   //cout<<koji[0].size()<<" "<<koji[1].size()<<" "<<koji[2].size()<<endl;
   for(int it=1;it<=N;it++)
      dodaj(odakle^1);
   while(koji[0].size()){
      V.push_back(koji[0].back());
      koji[0].pop_back();
   }
   //cout<<"CCC"<<endl;
   while(koji[1].size()){
      V.push_back(koji[1].back());
      koji[1].pop_back();
   }
   //cout<<"ROOT JE "<<root<<endl;
   V.push_back(root);
   for(int i=0;i<V.size();i++)
      V[i]--;
   return V;}

Compilation message (stderr)

fun.cpp: In function 'void spoj(int, int)':
fun.cpp:70:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |    for(int i=0;i<koji[b].size();i++)
      |                ~^~~~~~~~~~~~~~~
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:146:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |    for(int i=0;i<V.size();i++)
      |                ~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 34 / 34