제출 #349907

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
349907		Pety	경주 (Race) (IOI11_race)	C++14	0 / 100	10 ms	14464 KiB

race

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


using namespace std;

const int N = 2e5 + 2;
vector<pair<int, int> >G[N];
set<pair<int, int> > s[N];
int dist[N], edge[N], k;
int 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->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 = n;
  dfs(0, -1);
  return ans;
}

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