제출 #1202150

#제출 시각아이디문제언어결과실행 시간메모리
1202150ackhavaFun Tour (APIO20_fun)C++20
0 / 100
2097 ms31932 KiB
#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); // } REP(i,1,N){ adj[i].insert((i-1)/2); adj[(i-1)/2].insert(i); } 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); } if(dst.size()>=2){ REP(i,0,dst.size()-1){ assert(dst[i+1]<=dst[i]); } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...