Submission #748119

#	Time	Username	Problem	Language	Result	Execution time	Memory
748119		Prieved1	Race (IOI11_race)	C++17	100 / 100	519 ms	148120 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1000'010;
vector<pair<int,int>> g[N];
int n, k;
int sz[N], depth[N], dist[N];
map<long long, int> mn[N];
int res;
void getsz(int at, int p, long long sum=0, int d=0) {
  sz[at]=1;
  dist[at]=sum;
  depth[at]=d;
  for(auto to:g[at]) {
    if(to.first==p)continue;
    getsz(to.first, at, sum+to.second, d+1);
    sz[at]+=sz[to.first];
  }
}
void dfs(int at, int p) {
  for(auto [to,tmp]:g[at]) {
    if(to==p)continue;
    dfs(to,at);
    if(mn[to].size()>mn[at].size()) {
      swap(mn[to], mn[at]);
    }
    for(auto [dis, dep]:mn[to]) {
      long long y=k+2*dist[at]-dis;
      if(mn[at].find(y)!=mn[at].end()){
        res=min(res, mn[at][y]+dep-2*depth[at]);
      }
    }
    for(auto [dis, dep]:mn[to]) {
      if(mn[at][dis]==0)mn[at][dis]=dep;
      mn[at][dis]=min(mn[at][dis], dep);
    }
  }
  if(mn[at].find(dist[at]+k)!=mn[at].end()){
    res=min(res, mn[at][dist[at]+k]-depth[at]);
  }
  if(mn[at][dist[at]]!=0)mn[at][dist[at]]=min(mn[at][dist[at]], depth[at]);
  else mn[at][dist[at]]=depth[at];
}
int best_path(int _N, int _K, int H[][2], int L[])
{
  n=_N, k=_K;
  for(int i = 0;i<_N-1;i++) {
    g[H[i][0]].push_back({H[i][1],L[i]});
    g[H[i][1]].push_back({H[i][0],L[i]});
  }
  getsz(0,-1,0,1);
  res=1e9;
  dfs(0,-1);
  if(res==1e9)return -1;
  return res;
}
   

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