Submission #1214124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214124		loom	Fun Tour (APIO20_fun)	C++20	21 / 100	633 ms	170564 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;
int p[N];
vector<int> g[N];
map<int,int> dist[N];
set<pair<int,int>> st[N];

void dfs(int v){
   st[v].insert({0, v});

   for(int ch : g[v]){
      dfs(ch);
      for(auto &[d, u] : st[ch]) st[v].insert({d+1, u}), dist[v][u] = d+1; 
   }
}

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

   dfs(0);
   int x = 0;
   vector<int> ans;

   for(int i=0; i<n; i++){
      int v = x, pre = -1;
      pair<int,int> pr = {-1, -1};

      int d = 1;
      while(v != -1){
         pr = max(pr, {d-1, v});

         for(int ch : g[v]){
            if(ch == pre or st[ch].empty()) continue;
            auto [mx, u] = *st[ch].rbegin();
            pr = max(pr, {mx + d, u});
         }

         pre = v;
         v = p[v];
         d++;
      }

      auto [mx, u] = pr;
      ans.push_back(u);
      x = u;

      v = u;
      while(v != -1){
         st[v].erase({dist[v][u], u});
         v = p[v];
         d++;
      }
   }

   return ans;
}

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