Submission #1258628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258628		papaulo	Race (IOI11_race)	C++20	100 / 100	248 ms	80088 KiB

race

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

#define MAXN 200200
vector<pair<int, int>> adj[MAXN];
using ll = long long;
ll bonus[MAXN];
int sti[MAXN];
unordered_map<ll, int> mp[MAXN];

int ans=1e9;

ll k;

void dfs(int v, int p, int d) {
  int id=-1;
  for(auto e : adj[v]) {
    int u=e.first, w=e.second;
    if(u==p) continue;
    dfs(u, v, d+1);
    if(id<0||mp[sti[u]].size()>mp[id].size()) {
      id=sti[u];
      bonus[v]=bonus[u]+w;
    }
  }
  if(id<0) {
    id=v;
    bonus[v]=0LL;
  }
  for(auto e : adj[v]) {
    int u=e.first, w=e.second;
    if(u==p||sti[u]==id) continue;
    for(auto pr : mp[sti[u]]) {
      ll cur=pr.first+w+bonus[u];
      auto p = mp[id].find(k-cur-bonus[v]);
      if(p==mp[id].end()) continue;
      ans=min(ans, p->second+pr.second-2*d);
    }
    for(auto pr : mp[sti[u]]) {
      ll cur=pr.first+w+bonus[u]-bonus[v];
      auto p = mp[id].find(cur);
      if(p==mp[id].end()) {
        mp[id][cur]=pr.second;
      } else {
        p->second=min(p->second, pr.second);
      }
    }
  }
  auto p2 = mp[id].find(k-bonus[v]);
  if(p2!=mp[id].end()) {
    ans=min(ans, p2->second-d);
  }
  mp[id][-bonus[v]]=d;
  sti[v]=id;
}

int best_path(int N, int K, int H[][2], int L[])
{
  k=K;
  for(int i=0;i<N-1;i++) {
    int v=H[i][0], u=H[i][1], w=L[i];
    adj[v].push_back({u, w});
    adj[u].push_back({v, w});
  }
  dfs(0, -1, 0);
  if(ans==1e9) ans=-1;
  return ans;
}

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