Submission #776869

#	Time	Username	Problem	Language	Result	Execution time	Memory
776869		I_Love_EliskaM_	Race (IOI11_race)	C++14	100 / 100	424 ms	84628 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pi pair<int,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end()
const int inf=1e9;
int ans=inf;
const int N=2e5+5;
map<int,int> z[N];
int add1[N], add2[N];

vector<pi> adj[N];
int k;

void dfs(int u, int p) {
  z[u][0]=0;
  for(auto&e:adj[u]) {
    int v=e.f, w=e.s;
    if (v==p) continue;
    dfs(v,u);
    add1[v]++; add2[v]+=w;
    if (z[v].size()>z[u].size()) {
      swap(z[u],z[v]);
      swap(add1[u],add1[v]);
      swap(add2[u],add2[v]);
    }
    for(auto&it:z[v]) {
      int x=it.f, y=it.s;
      //x + add2[v] + add2[u] + len = k
      if (z[u].count(k-x-add2[v]-add2[u])) {
        ans=min(ans,z[u][k-x-add2[v]-add2[u]]+add1[u]+add1[v]+y);
      }
    }
    for(auto&it:z[v]) {
      int x=it.f, y=it.s;
      if (z[u].count(x+add2[v]-add2[u])) {
        z[u][x+add2[v]-add2[u]]=min(z[u][x+add2[v]-add2[u]],y+add1[v]-add1[u]);
      } else {
        z[u][x+add2[v]-add2[u]]=y+add1[v]-add1[u];
      }
    }
  }
}

int best_path(int n, int _k, int h[][2], int l[]) {
  k=_k;
  forn(i,n-1) {
    int u=h[i][0], v=h[i][1];
    adj[u].pb({v,l[i]}); adj[v].pb({u,l[i]});
  }
  dfs(0,-1);
  if (ans==inf) return -1;
  else return ans;
}

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