Submission #892048

#	Time	Username	Problem	Language	Result	Execution time	Memory
892048		NemanjaSo2005	Fun Tour (APIO20_fun)	C++17	0 / 100	0 ms	600 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+1)/2)
         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+1)/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[3^c^odakle].back()))
      dodaj(3^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) {
   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);
  // cout<<koji[0].size()<<" "<<koji[1].size()<<" "<<koji[2].size()<<endl;
   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()){
      //cout<<koji[0].size()<<" "<<koji[1].size()<<" "<<koji[2].size()<<endl;
      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<<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();
   }
   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;
}
/*
7 400000
0 1
0 5
0 6
1 2
1 4
2 3
*/

Compilation message (stderr)

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

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