Submission #1202136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202136		ackhava	Fun Tour (APIO20_fun)	C++20	26 / 100	56 ms	23108 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;

set<int> adj[200100];

pair<int,int> furthest(int node, int origin, int dst){
  pair<int,int> ans={dst,node};
  for(auto i:adj[node]){
    if(i!=origin)ans=max(ans,furthest(i,node,dst+1));
  }
  return ans;
}

std::vector<int> createFunTour(int N, int Q) {
  REP(i,0,N)REP(j,i+1,N){
    if(hoursRequired(i,j)==1)adj[j].insert(i),adj[i].insert(j);
  }
  int cur=furthest(1,-1,0).se;
  vector<int> ans;ans.pb(cur);
  vector<int> dst;
  REP(i,1,N){
    auto nxt=furthest(cur,-1,0);
    dst.pb(nxt.fi);
    for(auto i:adj[cur])adj[i].erase(cur);
    adj[cur].clear();
    cur=nxt.se;
    ans.pb(cur);
  }
  // cerr<<"! ";
  // for(auto i:ans)cerr<<i<<" ";
  // cerr<<endl;
  // cerr<<"!> ";
  // for(auto i:dst)cerr<<i<<" ";
  // cerr<<endl;
  if(dst.size()>=2){
    REP(i,0,dst.size()-1){
      assert(dst[i+1]<=dst[i]);
    }
  }
  return ans;
}

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