Submission #1277684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277684		DeltaStruct	Race (IOI11_race)	C++20	9 / 100	110 ms	7676 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);
        if (!dp[0].contains(a)) dp[0][a] = 1e18;
        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);
}

Compilation message (stderr)

race.cpp: In instantiation of 'best_path(int, int, int (*)[2], int*)::<lambda(auto:54, int, int, long long int, int)> [with auto:54 = best_path(int, int, int (*)[2], int*)::<lambda(auto:54, int, int, long long int, int)>]':
race.cpp:29:6:   required from here
race.cpp:20:44: warning: overflow in conversion from 'double' to 'std::map<long long int, int>::mapped_type' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   20 |         if (!dp[0].contains(a)) dp[0][a] = 1e18;
      |                                            ^~~~

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