Submission #185569

#	Time	Username	Problem	Language	Result	Execution time	Memory
185569		kdh9949	Race (IOI11_race)	C++17	0 / 100	14 ms	9976 KiB

race

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

using pii = pair<int, int>;
#define x first
#define y second

const int N = 200005;

int n, k, res = N;
vector<pii> e[N];

struct SET{
  set<pii> s;
  pii ofs;
  SET(): ofs(0, 0) { s.emplace(0, 0); }
};

SET *f(int x, int y){
  if(x && e[x].size() == 1) return new SET();
  vector<SET*> v;
  SET* mx = NULL;
  for(pii i : e[x]){
    if(i.x == y) continue;
    v.push_back(f(i.x, x));
    v.back()->ofs.x += i.y;
    v.back()->ofs.y++;
    if(!mx || mx->s.size() < v.back()->s.size()) mx = v.back();
  }
  for(SET* i : v){
    if(i == mx) continue;
    for(pii j : i->s){
      auto it = mx->s.lower_bound(pii(k - (j.x + i->ofs.x), -N));
      if(it->x + mx->ofs.x + j.x + i->ofs.x == k)
        res = min(res, it->y + mx->ofs.y + j.y + i->ofs.y);
    }
    for(pii j : i->s){
      pii cur(j.x + i->ofs.x - mx->ofs.x, j.y + i->ofs.y - mx->ofs.y);
      auto it = mx->s.lower_bound(pii(cur.x, -N));
      if(it != mx->s.end() && it->x == cur.x){
        if(it->y <= cur.y) continue;
        if(it->y > cur.y) mx->s.erase(it);
      }
      mx->s.insert(cur);
    }
  }
  set<pii> t;
  while(mx->s.rbegin()->x + mx->ofs.x > k) mx->s.erase(*mx->s.rbegin());
  mx->s.emplace(-mx->ofs.x, -mx->ofs.y);

  auto it = mx->s.lower_bound(pii(k - mx->ofs.x, -N));
  if(it != mx->s.end() && it->x + mx->ofs.x == k) res = min(res, it->y + mx->ofs.y);

  return mx;
}

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

  f(0, -1);
  return (res == ::N ? -1 : res);
}

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