Submission #965805

#TimeUsernameProblemLanguageResultExecution timeMemory
965805Darren0724Fun Tour (APIO20_fun)C++17
10 / 100
9 ms7516 KiB
#include "fun.h" #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(),x.end() const int N=200005; int cntid=0; vector<int> adj[N],sz(N,1),pa(N),ans,dis(N); priority_queue<pair<int,int>> pq[3]; void dfs(int k){ for(int j:adj[k]){ if(j==pa[k])continue; pa[j]=k; dfs(j); sz[k]+=sz[j]; } } int cen(int k,int need){ for(int j:adj[k]){ if(j==pa[k])continue; if(sz[j]>=need)return cen(j,need); } return k; } void dfs1(int k,int pa){ pq[cntid].push({dis[k],k}); for(int j:adj[k]){ if(j==pa)continue; dis[j]=dis[k]+1; dfs1(j,k); } } vector<int> createFunTour(int n, int q) { //int H = hoursRequired(0, N - 1); //int A = attractionsBehind(0, N - 1); for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ if(hoursRequired(i,j)==1){ adj[i].push_back(j); adj[j].push_back(i); } } } dfs(0); int c1=cen(0,(n+1)/2); for(int j:adj[c1]){ dfs1(j,c1); cntid++; } int last=-1; for(int i=1;i<n;i++){ pair<int,int> p={-1,-1}; for(int j=0;j<cntid;j++){ if(j==last)continue; p=max(p,make_pair((int)pq[j].size(),j)); } last=p.second; auto [dis1,idx]=pq[p.second].top(); pq[p.second].pop(); ans.push_back(idx); } ans.push_back(c1); 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...