제출 #1277716

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277716		DeltaStruct	경주 (Race) (IOI11_race)	C++20	21 / 100	3093 ms	21816 KiB

race

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

int best_path(int n,int m,int H[][2],int L[]){
  vector<vector<pair<int,int>>> G(n); for (int i(0);i < n-1;++i){
    G[H[i][0]].emplace_back(H[i][1],L[i]),G[H[i][1]].emplace_back(H[i][0],L[i]);
  }
  int r = n;
  auto dfs = [&](auto dfs,int x,int p,long long d,int dd) -> map<long long,int> {
    vector<map<long long,int>> dp;
    for (auto [y,z]:G[x]) if (y!=p) dp.emplace_back(dfs(dfs,y,x,d+z,dd+1));
    sort(dp.begin(),dp.end(),[](auto& a,auto& b){
      return a.size()>b.size();
    });
    if (dp.empty()) dp.emplace_back();
    while(dp.size()>1){
      for (auto [a,b]:dp.back()) if (dp[0].contains(m-a+2*d)) r = min(r,b+dp[0][m-a+2*d]-2*dd);
      for (auto [a,b]:dp.back()){
        if (!dp[0].contains(a)) dp[0][a] = 1e9;
        dp[0][a] = min(dp[0][a],b);
      }
      dp.pop_back();
    }
    for (auto [a,b]:dp[0]) if (a-d==m) r = min(r,b-dd);
    dp[0][d] = dd;
    return dp[0];
  };
  dfs(dfs,0,-1,0,0);
  return (r==n?-1:r);
}

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