Submission #349917

#	Time	Username	Problem	Language	Result	Execution time	Memory
349917		Pety	Race (IOI11_race)	C++14	100 / 100	535 ms	114284 KiB

race

#include <bits/stdc++.h>
#include "race.h"


using namespace std;

const int N = 2e5 + 2;
vector<pair<int, long long> >G[N];
set<pair<long long, int> > s[N];
long long dist[N], edge[N], k;
long long ans;

///a + b - 2 * dist

void dfs (int nod, int p) {
  s[nod].insert({dist[nod], edge[nod]});
  for (auto it : G[nod]) {
    if (it.first == p)
      continue;
    dist[it.first] = dist[nod] + it.second;
    edge[it.first] = edge[nod] + 1;
    dfs(it.first, nod);
    if (s[nod].size() < s[it.first].size())
      swap(s[nod], s[it.first]);
    for (auto it2 : s[it.first]) {
      auto meh = s[nod].lower_bound({k - it2.first + 2 * dist[nod], 0});
      if (meh != s[nod].end() && meh->first + it2.first -2 * dist[nod] == k) {
        ans = min(ans, it2.second + (*meh).second - 2 * edge[nod]);
      }
    }
    for (auto it2 : s[it.first])
      s[nod].insert(it2);
  }
}

int best_path (int n, int K, int h[][2], int l[]) {
  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]});
  }
  k = K;
  ans = 1e9;
  dfs(0, -1);
  if (ans == 1e9)
    return -1;
  return ans;
}

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