Submission #1133431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133431		alecurse	Race (IOI11_race)	C++20	100 / 100	307 ms	79936 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
int bestres=1e9;
vector<vector<pair<int,int> > > adj;
vector<pair<unordered_map<int,int>, int> > v;
void dfs(int x, int e, int dph, int K) {
  for(auto el : adj[x]) {
    int b = el.first, w = el.second;
    if(b==e)
      continue;
    dfs(b,x,dph+1,K);
    v[b].first[-v[b].second]=dph+1;
    v[b].second+=w;
    if(v[b].first.size()>v[x].first.size()) {
      swap(v[b],v[x]);
    }
    if(v[x].first.count(K-v[x].second)) {
      bestres=min(bestres,v[x].first[K-v[x].second]-dph);
    }
    if(v[b].first.count(K-v[b].second)) {
      bestres=min(bestres,v[b].first[K-v[b].second]-dph);
    }
    for(auto el : v[b].first) {
      int realel = el.first+v[b].second;
      if(v[x].first.count(K-realel-v[x].second)) {
        bestres=min(bestres,v[x].first[K-realel-v[x].second]+el.second-2*dph);
      }
    }
    for(auto el : v[b].first) {
      int realel = el.first+v[b].second;
      if(v[x].first.count(realel-v[x].second)) {
        v[x].first[realel-v[x].second]=min(v[x].first[realel-v[x].second],el.second);
      } else {
        v[x].first[realel-v[x].second]=el.second;
      }
    }
  }
}

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

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