Submission #1326547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326547		rainerevan_	Race (IOI11_race)	C++20	0 / 100	3096 ms	14392 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 5;
const ll LOG = 30;
#define vll vector <ll>
#define pll pair <ll, ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " " << (x) << endl;

ll n, k;
vector <vector <pll> > adj (MAXN);
ll ans = INF;
ll dp [MAXN], dep [MAXN];
vector <set <pll>> st (MAXN);

void tun(ll x, ll v, ll dmn){
  // k = v + ... - 2*dp[x]
  // k + 2*dp[x] - v = ...
  ll cnt = k + 2*dp[x] - v;
  auto it = st[x].lower_bound({cnt, 0});
  if((*it).fi == cnt){
    ans = min(ans, dmn+(*it).se-2*dep[x]);
  }
}
void add(ll x, ll v, ll dmn){
  auto it = st[x].lower_bound({v, 0});
  if((*it).fi == v){
    dmn = min(dmn, (*it).se);
    st[x].erase(it);
  }
  st[x].insert({v, dmn});
}

void dfs(ll x, ll px){
  for(auto [y, w] : adj[x]){
    if(y == px) continue;
    dp[y] = dp[x] + w;
    dep[y] = dep[x] + 1;
    dfs(y, x);
    if((ll)st[x].size() < (ll)st[y].size()) swap(st[x], st[y]);
    for(auto [v, dmn] : st[y]) tun(x, v, dmn);
    for(auto [v, dmn] : st[y]) add(x, v, dmn);
  }
  // debug(x)
  // debug(dp[x])
  // debug(dep[x])
  // for(auto [v, dmn] : st[x]){
  //   cout << v << " " << dmn << endl;
  // }
  tun(x, dp[x], dep[x]);
  add(x, dp[x], dep[x]);
}

int best_path(int N, int K, int H[][2], int L[])
{
  n = N;
  k = K;
  for(ll i = 0; i < n-1; i++){
    auto [u, v] = H[i];
    ll w = L[i];
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }
  dfs(0, -1);
  return (ans == INF) ? -1 : ans;
}

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