제출 #1312801

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312801		tsetsenbileg	Race (IOI11_race)	C++20	21 / 100	455 ms	327680 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
using pr = pair<int, int>;
const int INF = 1e9+7, MOD = 1e9+7;
int n, k;
vector<vector<pr>> edge;
vector<map<int, int>> dp; // node, [sum of distance, {+ -}]

int ans;

void dfs(int node, int par) {
  dp[node][0] = 0;
  for (auto [next, d] : edge[node]) {
    if (next == par) continue;
    dfs(next, node);
    for (auto [i, cnt] : dp[next]) {
      long long dist = (long long)i + d;
      if (dist > k) continue;
      int need = k - (int)dist;
      if (dp[node].count(need)) {
        ans = min(ans, cnt + 1 + dp[node][need]);
      }
    }
    for (auto [i, cnt] : dp[next]) {
      long long dist = (long long)i + d;
      if (dist > k) continue;
      if (!dp[node].count((int)dist) || dp[node][(int)dist] > cnt + 1) {
        dp[node][(int)dist] = cnt + 1;
      }
    }
  }
}

int best_path(int N, int K, int h[][2], int l[]) {
  n = N; k = K;
  ans = INF;
  edge.assign(n, vector<pr>());
  dp.assign(n, map<int,int>());
  for (int i = 0; i < n-1; i++) {
    edge[h[i][0]].pb({h[i][1], l[i]});
    edge[h[i][1]].pb({h[i][0], l[i]});
  }
  dfs(0, -1);
  return ans == INF ? -1 : ans;
}

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