제출 #236383

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236383		Haunted_Cpp	경주 (Race) (IOI11_race)	C++17	31 / 100	332 ms	114552 KiB

race

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


using namespace std;

const int MAX_N = 2e5 + 5;
const int MAX_K = 1e2 + 5;

vector< vector<pair<int, int> > > g (MAX_N);
int dp [MAX_N][MAX_K];

int delta;
int mn = numeric_limits<int>::max();

void dfs (int node, int p = -1) {
  for (auto to : g[node]) {
    if (to.first != p) dfs (to.first, node);
  }
  dp[node][0] = 0;
  for (auto to : g[node]) {
    if (to.first == p) continue;
    int vertex = to.first;
    int w = to.second;
    // Do with the others
    for (int i = 0; i <= delta; i++) {
      int other = delta - i - w;
      if (other >= 0) mn = min (mn, dp[node][i] + dp[vertex][other] + 1);
    }
    // Add path
    for (int i = 0; i <= delta; i++) {
      if (i - w >= 0) dp[node][i] = min (dp[node][i], 1 + dp[vertex][i - w]);
    }
  }
  mn = min (mn, dp[node][delta]);
}

int best_path(int N, int K, int H[][2], int L[]) {
  delta = K;
  for (int i = 0; i < N - 1; i++) {
    int st = H[i][0];
    int et = H[i][1];
    int w = L[i];
    g[st].emplace_back(et, w);
    g[et].emplace_back(st, w);
  }
  for (int i = 0; i < MAX_N; i++) {
    for (int j = 0; j < MAX_K; j++) {
      dp[i][j] = 1e9;
    }
  }
  dfs (0);
  return (mn > 1e8 ? -1 : mn);
}

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