제출 #500608

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
500608		Joo	경주 (Race) (IOI11_race)	C++17	0 / 100	7 ms	14412 KiB

race

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

const int INF = 1e9, MAXN = 2e5+10;

int ans = MAXN;
map<long long, int> mp[MAXN];
vector<pair<int,int>> G[MAXN];

void dfs(int u, int p, int dep, long long d, long long K){
  mp[u][d] = dep;
  for(auto [v, w] : G[u]){
    if(v == p) continue;
    dfs(v, u, dep+1, d+w, K);

    if(mp[v].size() > mp[u].size()) swap(mp[v], mp[u]);
    for(auto [key, val] : mp[v]){
      long long tmp = K-key+2*dep;
      if(mp[u].count(tmp)) ans = min(ans, val+mp[u][tmp]-2*dep);
    }
    for(auto [key, val] : mp[v]){
      if(mp[u].count(key)) mp[u][key] = min(mp[u][key], val);
      else mp[u][key] = val;
    }
  }

  if(mp[u].count(K+d)) ans = min(ans, mp[u][K+d]-dep);

}

int best_path(int MAXN, int K, int H[][2], int L[])
{
  for(int i = 0; i < MAXN-1; i++){
    int u = H[i][0], v = H[i][1];
    G[u].emplace_back(v, L[i]);
    G[v].emplace_back(u, L[i]);
  }

  dfs(0, -1, 0, 0, K);

  if(ans >= MAXN) ans = -1;
  return ans;
}

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