Submission #1202238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202238		ackhava	Fun Tour (APIO20_fun)	C++20	40 / 100	772 ms	196200 KiB

fun

#include "fun.h"
#pragma GCC optimize "O3,unroll-loops"
#pragma GCC target "abm,bmi,bmi2,popcnt,lzcnt,avx,avx2"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all(v) begin(v), end(v)
#define REP(i,o,n) for(int i=o;i<n;i++)
using namespace std;

vector<int> tiers[200100];
int par[200100];
int lkx[200100];
bool zd;
set<pair<int,int>> mp[200100][4];

pair<int,int> furthest(int node){
  pair<int,int> ans={-1,node};
  for(auto i:mp[node])if(i.size())ans=max(ans,*i.rbegin());
  int cur=node;
  int dst=0;
  while(cur){
    auto pxt=par[cur];
    ++dst;
    REP(i,0,4)if(i!=lkx[cur] && mp[pxt][i].size())ans=max(ans,{mp[pxt][i].rbegin()->fi + dst, mp[pxt][i].rbegin()->se});
    cur=pxt;
  }
  // cerr<<"FURTHEST FROM "<<node<<": "<<ans.se<<" (DISTANCE: "<<ans.fi<<")\n";
  return ans;
}

std::vector<int> createFunTour(int N, int Q) {
  memset(par,-1,sizeof par);
  REP(i,0,N+10)tiers[i].clear(),mp[i][0].clear(),mp[i][1].clear(),mp[i][2].clear(),mp[i][3].clear();
  tiers[0].pb(0);
  REP(i,1,N){
    tiers[hoursRequired(0,i)].pb(i);
  }
  REP(i,0,N+10)sort(all(tiers[i]));
  REP(i,1,N+10){
    if(!tiers[i].size())break;
    int cur=0;
    for(auto j:tiers[i]){
      while(cur<tiers[i-1].size() && hoursRequired(tiers[i-1][cur],j)!=1)cur++;
      assert(cur<tiers[i-1].size());
      par[j]=tiers[i-1][cur];
    }
  }
  REP(i,0,N+10)tiers[i].clear();
  REP(i,1,N){
    tiers[par[i]].pb(i);
  }
  REP(i,0,N){
    REP(j,0,tiers[i].size()){
      lkx[tiers[i][j]]=j;
      // cerr<<tiers[i][j]<<" -> "<<j<<endl;
    }
  }
  REP(i,0,N){
    int cur=i;
    int dst=0;
    while(cur){
      auto pxt=par[cur];
      mp[pxt][lkx[cur]].insert({++dst,i});
      cur=pxt;
    }
    mp[i][3].insert({0,i});
  }
  vector<int> ans;
  int fnd=furthest(0).se;
  ans.pb(fnd);
  REP(_,1,N){
    auto nxt=furthest(fnd);
    int cur=fnd;
    int dst=0;
    while(cur){
      auto pxt=par[cur];
      mp[pxt][lkx[cur]].erase({++dst,fnd});
      cur=pxt;
    }
    mp[fnd][3].erase({0,fnd});
    ans.pb(fnd=nxt.se);
    // cerr<<"! "<<nxt.se<<endl;
  }
  return ans;
}

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