Submission #378662

#	Time	Username	Problem	Language	Result	Execution time	Memory
378662		Gilgamesh	Race (IOI11_race)	C++17	43 / 100	418 ms	89452 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define all(x) (x).begin(),(x).end()
#define pb push_back

const int mxN = 300000;
const int ninf = -1e18;

int k;
vector<array<int, 2>> adj[mxN];
multiset<array<int, 2>> paths[mxN];
array<int, 2> add[mxN];
int ans;

void dfs(int v, int p) {
  for(auto[i, w] : adj[v]) {
    if(i == p) continue;
    dfs(i, v);
    add[i][0] += w;
    ++add[i][1];
    if(paths[i].size() > paths[v].size()) {
      add[i].swap(add[v]);
      paths[i].swap(paths[v]);
    }
    for(auto[len, edges] : paths[i]) {
      int cur = len + add[i][0];
      array<int, 2> search = {k - cur - add[v][0], ninf};
      auto lb = paths[v].upper_bound(search);
      if(lb != paths[v].end() && (*lb)[0] + add[v][0] + cur == k) {
        ans = min(ans, edges + add[i][1] + (*lb)[1] + add[v][1]);
      }
      search = {len + add[i][0] - add[v][0], ninf};
      lb = paths[v].lower_bound(search);
      if(lb == paths[v].end() || (*lb)[0] != len + add[i][0] - add[v][0] || (*lb)[1] > edges + add[i][1] - add[v][1]) {
      	paths[v].insert({len + add[i][0] - add[v][0], edges + add[i][1] - add[v][1]});
      }
    }
    paths[i].clear();
  }
  array<int, 2> find = {k - add[v][0], ninf};
  auto lb = paths[v].upper_bound(find);
  if(lb != paths[v].end() && (*lb)[0] + add[v][0] == k) {
    ans = min(ans, (*lb)[1] + add[v][1]);
  }
  find = {-add[v][0], ninf};
  lb = paths[v].lower_bound(find);
  if(lb == paths[v].end() || (*lb)[0] != -add[v][0] || (*lb)[1] > -add[v][1]) {
	  paths[v].insert({-add[v][0], -add[v][1]});
	}
}

int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[]) {
  k = K;
  ans = 1e18;
  for(int i = 0; i < N - 1; ++i) {
    adj[H[i][0]].pb({H[i][1], L[i]});
    adj[H[i][1]].pb({H[i][0], L[i]});
  }
  dfs(0, -1);
  return ans == 1e18 ? -1 : ans;
}
/*
signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int N, K; cin >> N >> K;
  int H[N - 1][2], L[N - 1];
  for(int i = 0; i < N - 1; ++i) {
    cin >> H[i][0] >> H[i][1] >> L[i];
  }
  cout << best_path(N, K, H, L) << "\n";
}
*/

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