Submission #1202249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202249		adiyer	Race (IOI11_race)	C++20	100 / 100	466 ms	58112 KiB

race

#pragma once

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define len(s) (ll) s.size()
#define pb push_back
#define S second
#define F first

using namespace std;

typedef int ll;

const int MXN = 2e5 + 11;
const long long inf = 1e18 + 11;

ll n, m, res, lng;
ll sz[MXN], mrk[MXN], d[MXN];

vector < pair < ll, ll > > g[MXN];

multiset < pair < long long, ll > > st;

long long val;
long long path[MXN];

void sizes(ll v, ll p){
  sz[v] = 1;
  for(auto [u, w] : g[v])
    if(u != p)
      d[u] = d[v] + 1, 
      path[u] = path[v] + w,
      sizes(u, v), 
      sz[v] += sz[u];
}

void add(ll v, ll p, ll x){
  for(auto [u, w] : g[v])
    if(u != p && !mrk[u])
      add(u, v, x);
  if(x) st.insert({path[v], d[v]});
  else st.erase(st.find({path[v], d[v]})); 
}

void calc(ll v, ll p, ll lca){
  val = lng + 2 * path[lca] - path[v];
  auto it = st.lower_bound({val, 0});
  if(it != st.end() && (it -> F) == val) res = min(res, d[v] + (it -> S) - 2 * d[lca]);
  for(auto [u, w] : g[v])
    if(u != p && !mrk[u])
      calc(u, v, lca);
}

void small_to_large(ll v, ll p, bool keep){
  ll big_child = -1;
  for(auto [u, w] : g[v])
    if(u != p && (big_child == -1 || sz[u] > sz[big_child]))
        big_child = u;
  for(auto [u, w] : g[v])
    if(u != p && u != big_child)
      small_to_large(u, v, 0);
  if(big_child != -1) 
    small_to_large(big_child, v, 1), mrk[big_child] = 1;
  st.insert({path[v], d[v]});
  for(auto [u, w] : g[v])
    if(u != p && !mrk[u])
      calc(u, v, v),
      add(u, v, 1);
  if(big_child != -1)
    mrk[big_child] = 0;
  val = lng + path[v];
  auto it = st.lower_bound({val, 0});
  if(it != st.end() && (it -> F) == val) res = min(res, (it -> S) - d[v]);
  if(!keep){
    for(auto [u, w] : g[v])
      if(u != p && !mrk[u])
        add(u, v, 0);  
    st.erase(st.find({path[v], d[v]})); 
  }
}

int best_path(int N, int K, int H[][2], int L[]){
  lng = K, res = MXN;
  for(ll i = 0; i < N - 1; i++)
    g[H[i][0]].pb({H[i][1], L[i]}),
    g[H[i][1]].pb({H[i][0], L[i]});
  sizes(0, 0);
  small_to_large(0, 0, 0);
  if(res == MXN) res = -1;
  return res;
}

Compilation message (stderr)

race.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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