제출 #1202183

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1202183		ackhava	Fun Tour (APIO20_fun)	C++20	0 / 100	2098 ms	123932 KiB

fun

#include "fun.h"
#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];
map<int,set<pair<int,int>>> mp[200100];

pair<int,int> furthest(int node){
  pair<int,int> ans={-1,node};
  for(auto i:mp[node])if(i.se.size())ans=max(ans,*i.se.rbegin());
  int cur=node;
  int dst=0;
  while(cur){
    auto pxt=par[cur];
    ++dst;
    for(auto i:mp[pxt])if(i.fi!=cur && i.se.size())ans=max(ans,{i.se.rbegin()->fi + dst, i.se.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].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){
    int cur=i;
    int dst=0;
    while(cur){
      auto pxt=par[cur];
      mp[pxt][cur].insert({++dst,i});
      cur=pxt;
    }
    mp[i][-1].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][cur].erase({++dst,fnd});
      cur=pxt;
    }
    mp[fnd][-1].erase({0,fnd});
    ans.pb(fnd=nxt.se);
    // cerr<<"! "<<nxt.se<<endl;
  }
  return ans;
}

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