제출 #543862

#제출 시각아이디문제언어결과실행 시간메모리
543862AJ00경주 (Race) (IOI11_race)C++14
9 / 100
3058 ms42968 KiB
#include <bits/stdc++.h> #include "race.h" using namespace std; //#define ll long long #define ll long long const ll MAXN = 200001; const ll LOGN = 20; vector<vector<pair<ll,ll>>> adj(MAXN); int depth[MAXN]; ll par[MAXN][LOGN],weight[MAXN][LOGN]; pair<ll,int> lca(ll x, ll y){ ll X = x, Y = y; if (depth[X] < depth[Y]){ swap(x,y); swap(X,Y); } ll dh = depth[x]-depth[y]; ll totw = 0; for (ll i = LOGN-1; i >= 0; i--){ if (dh&(1<<i)){ totw += weight[x][i]; x = par[x][i]; } } if (x == y){ return {totw, depth[X]-depth[Y]}; } int lvl = 0; for (ll i = LOGN; i >= 0; i--){ if (par[x][i] != par[y][i]){ totw += weight[x][i]; totw += weight[y][i]; lvl += (1<<i); x = par[x][i]; y = par[y][i]; } } totw += weight[x][0]; totw += weight[y][0]; lvl += 1; lvl *= 2; return {totw,lvl+depth[X]-depth[Y]}; } void dfs(ll x, ll h = 0, ll p= 0, ll w = 0){ depth[x] = h; par[x][0] = p; weight[x][0] = w; for (ll i = 1; i < LOGN; i++){ par[x][i] = par[par[x][i-1]][i-1]; weight[x][i] = weight[x][i-1] + weight[par[x][i-1]][i-1]; } for (auto ch: adj[x]){ ll t = ch.first; ll wt = ch.second; if (t != p){ dfs(t,h+1,x,wt); } } } int best_path(int N,int K,int H[][2],int L[]){ for (ll i = 0; i < N-1; i++){ adj[H[i][0]].push_back({H[i][1],L[i]}); adj[H[i][1]].push_back({H[i][0],L[i]}); } dfs(0); int ans = N; for (ll i = 0; i < N; i++){ for (ll j = i+1; j < N; j++){ pair<ll,int> l = lca(i,j); if (l.first == K){ // cout << i << " " << j << " " << depth[i] << " " << depth[j] << "\n"; ans = min(ans,l.second); } } } ans -= (ans == N ? N+1 : 0); 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...