Submission #788776

#	Time	Username	Problem	Language	Result	Execution time	Memory
788776		vjudge1	경주 (Race) (IOI11_race)	C++17	100 / 100	428 ms	54880 KiB

race

#include "bits/stdc++.h"

using namespace std;

#define ll long long
#define ii pair<int,int>
const int ms = 2e5 + 10;


ll dis[ms], ans, k, n, sz[ms], h[ms];
vector<ii> g[ms];

map<ll, ll> mp;

void insere(int u){
  if(mp.find(dis[u]) != mp.end()) mp[dis[u]] = min(mp[dis[u]], h[u]);
  else mp[dis[u]] = h[u];
}

void put(int u, int p){
  insere(u);
  for(auto [v, w] : g[u]){
    if(v == p) continue;
    put(v, u);
  } 
}

void qry(int u, int p, int q){
  if(mp.find(2ll*dis[q] - dis[u] + k) != mp.end()){
    ll now = mp[2ll*dis[q] - dis[u] + k] + h[u] - 2*h[q];
    if(ans == -1 || ans > now) ans = now;
  }

  for(auto [v, w] : g[u]){
    if(v == p) continue;
    qry(v, u, q);
  }
}


void dfs(int u=0, int p=-1, bool keep = false){
  int big = -1;
  for(auto [v, w] : g[u]){
    if(v == p) continue;
    if(big == -1 || sz[big] < sz[v]) big = v;
  }

  for(auto [v, w] : g[u]){
    if(v == p || v == big) continue;
    dfs(v, u, false);
  }

  if(big != -1) dfs(big, u, true);

  if(mp.find(2ll*dis[u] - dis[u] + k) != mp.end()){
    ll now = mp[2ll*dis[u] - dis[u] + k] + h[u] - 2*h[u];
    if(ans == -1 || ans > now) ans = now;
  }
  insere(u);
  
  for(auto [v, w] : g[u]){
    if(v == p || v == big) continue;
    qry(v, u, u);
    put(v, u);
  }

  if(!keep) mp.clear();
}

int getSz(int u=0, int p=-1, ll d=0, int height =0){
  sz[u] = 1;
  h[u] = height;
  dis[u] = d;
  for(auto [v, w] : g[u]){
    if(v == p) continue;
    sz[u] += getSz(v, u, d+w, height +1);
  }
  return sz[u];
}

int best_path(int N, int K, int H[][2], int L[]){
  k = K;
  n = N;
  for(int i=0; i<n-1; i++){
    g[H[i][0]].push_back({H[i][1], L[i]});
    g[H[i][1]].push_back({H[i][0], L[i]});
  }

  ans = -1;
  getSz();
  dfs();
  return ans;
}

// signed main(){
//   cin.tie(0);
//   ios::sync_with_stdio(0);

//   cin >> n >> k;

//   for(int i=1; i<n; i++){
//     int a, b, w;
//     cin >>a >> b >> w;
//     g[a].push_back(ii(b, w));
//     g[b].push_back(ii(a, w));
//   }
//   ans = -1;
//   getSz();
//   dfs();

//   cout << ans << endl;
// }

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57