Submission #1214089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214089		loom	Fun Tour (APIO20_fun)	C++20	0 / 100	2 ms	2632 KiB

fun

#include "fun.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 5e18
#define nl '\n'

const int N = 1e5;
vector<int> g[N];
int vis[N];
int mx, x;

void dfs(int v, int p, int d){
   if(d > mx){
      mx = d;
      x = v;
   }

   for(int ch : g[v]){
      if(ch != p) dfs(ch, v, d+1);
   }
}

vector<int> createFunTour(int n, int q){
   if(n <= 500){
      for(int i=0; i<n; i++){
         for(int j=i+1; j<n; j++){
            if(hoursRequired(i, j) == 1){
               g[i].push_back(j);
               g[j].push_back(i);
            }
         }
      }
   }
   else{
      for(int i=1; i<n; i++){
         int x = (i-1)/2;
         g[i].push_back(x);
         g[x].push_back(i);
      }
   }

   dfs(0, -1, 0);
   int y = x;

   mx = 0;
   dfs(y, -1, 0);

   int t = 0;
   vector<int> ans;

   while(ans.size() < n){
      int &v = t ? y : x;
      int nv = t ? x : y;
      ans.push_back(v);
      vis[v] = 1;
      t = !t;
      
      v = g[v][0];
      int c1 = -1, c2 = -1;
      for(int ch : g[v]){
         if(vis[ch]) continue;
         if(c1 == -1) c1 = ch;
         else c2 = ch;
      }

      if(c2 == -1) continue;
      if(hoursRequired(nv, c1) > hoursRequired(nv, c2)) v = c1;
      else v = c2;
   }

   return ans;
}

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