제출 #980471

#제출 시각아이디문제언어결과실행 시간메모리
980471Tuanlinh123즐거운 행로 (APIO20_fun)C++17
47 / 100
102 ms16332 KiB
#include "fun.h" #include<bits/stdc++.h> #define ll int #define pll pair<ll, ll> #define pb push_back #define mp make_pair #define fi first #define se second #define ld long double #define sz(a) ((ll)(a).size()) using namespace std; const ll maxn=100005; ll dist(ll a, ll b) {return hoursRequired(a, b);} ll subcnt(ll a, ll b) {return attractionsBehind(a, b);} vector<int> createFunTour(int n, int Q) { ll g=0; // findcentroid { ll cr=n; for (ll j=1; j<n; j++) { ll x=subcnt(0, j); if (x*2>n && x<cr) g=j, cr=x; } } vector <ll> d(n, 0); vector <pll> dis; vector <vector <pll>> branch; for (ll i=0; i<n; i++) if (i!=g) { dis.pb({dist(g, i), i}), d[i]=dis.back().fi; if (dis.back().fi==1) branch.pb(vector <pll> {{1, i}}), dis.pop_back(); } for (auto [d, i]:dis) for (ll j=0; j<sz(branch); j++) { if (j+1==sz(branch)) branch[j].pb({d, i}); else if (dist(i, branch[j][0].se)+1==d) {branch[j].pb({d, i}); break;} } for (ll j=0; j<sz(branch); j++) sort(branch[j].begin(), branch[j].end(), greater<pll>()); vector <ll> tour; if (sz(branch)==3) { // case 2 ll ptr[3]={}, last=-1, fat=0; while (1) { // check { ll sum=0, ok=1; for (ll i=0; i<3; i++) sum+=sz(branch[i])-ptr[i]; for (ll i=0; i<3; i++) if ((sz(branch[i])-ptr[i])*2>=sum) fat=i, ok=0; if (!ok || !sum) break; } ll big=-1; for (ll i=0; i<3; i++) if (i!=last && ptr[i]<sz(branch[i])) if (big==-1 || branch[big][ptr[big]]<branch[i][ptr[i]]) big=i; tour.pb(branch[big][ptr[big]].se), ptr[big]++, last=big; } vector <pll> b1, b2; for (ll i=0; i<3; i++) { if (i==fat) b1.insert(b1.end(), branch[i].begin()+ptr[i], branch[i].end()); else b2.insert(b2.end(), branch[i].begin()+ptr[i], branch[i].end()); } branch[0]=b1, branch[1]=b2; for (ll j=0; j<sz(branch); j++) sort(branch[j].begin(), branch[j].end(), greater<pll>()); } else if (sz(branch[0])<sz(branch[1])) swap(branch[0], branch[1]); ll lastdis=sz(tour)>=2?d[tour[sz(tour)-1]]+d[tour[sz(tour)-2]]:1e9; for (ll ptr[2]={}, t=0; ptr[0]<sz(branch[0]) || ptr[1]<sz(branch[1]); ptr[t]++, t^=1) { if (!ptr[0] && !ptr[1] && sz(tour) && dist(tour.back(), branch[t][ptr[t]].se)>lastdis) t^=1; tour.pb(branch[t][ptr[t]].se); } tour.pb(g); return tour; }
#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...