Submission #892038

#	Time	Username	Problem	Language	Result	Execution time	Memory
892038		NemanjaSo2005	Fun Tour (APIO20_fun)	C++17	0 / 100	0 ms	344 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int N,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)
         root=i;
   return;
}
void finddepth(){
  // for(int i=1;i<=N;i++)
  ////    for(int j=1;j<=N;j++)
   //      cout<<"DIST "<<i<<" "<<j<<" "<<hoursRequired(i-1,j-1)<<endl;
   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){
   return attractionsBehind(a-1,b-1)>=N/2;
}
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();
   return;
}
void spoj(int a,int b){
   int c=a^b^3;
   if(dist(V.back(),koji[c].back())<dist(koji[c].back(),koji[2^c^odakle].back()))
      dodaj(2^odakle^c);
   if(a>b)
      swap(a,b);
   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(b==1){
      koji[1]=koji[2];
      if(odakle==2)
         odakle=1;
   }
   koji[2].clear();
   if(odakle==b)
      odakle=a;
}
vector<int> createFunTour(int n, int Q) {
 //  cout<<hoursRequired(0,3)<<endl;
 //  return {};
   N=n;
   findroot();
   //cout<<"ROOT JE "<<root<<endl;
   finddepth();
   findsubtree();
   for(int i=0;i<=2;i++)
      if(koji[i].size())
         sort(koji[i].begin(),koji[i].end(),podub);
   if(koji[0].size()>=koji[1].size() and koji[0].size()>=koji[2].size())
      dodaj(0);
   else if(koji[1].size()>=koji[0].size() and koji[1].size()>=koji[2].size())
      dodaj(1);
   else
      dodaj(2);
   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);
   }
   for(int it=1;it<=N;it++)
      dodaj(odakle^1);
   //cout<<"ROOT JE "<<root<<endl;
   V.push_back(root);
   return V;
}

Compilation message (stderr)

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

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