Submission #428321

#	Time	Username	Problem	Language	Result	Execution time	Memory
428321		pliam	Race (IOI11_race)	C++14	100 / 100	1809 ms	51916 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 200005
#define INF (int)1e9

int ans;
ll k;
map<ll,int> existing,to_add;//(length, min number of edges)
vector<pair<int,ll>> adj[MAXN];//(to,weight)
bool rem[MAXN];//removed during centroid decomposition
int size[MAXN];

int dfs_sz(int curr,int par=-1){//compute sizes
  size[curr]=1;
  for(auto p:adj[curr]){
    int to=p.first;
    if(to==par||rem[to]) continue;
    size[curr]+=dfs_sz(to,curr);
  }
  return size[curr];
}

int centroid(int curr,int par,int n){
  for(auto p:adj[curr]){
    int to=p.first;
    if(to==par||rem[to]) continue;
    if(size[to]>n/2) return centroid(to,curr,n);
  }
  return curr;
}

void dfs2(int curr,int par,int num,int len){//paths starting from curr
  if(to_add.count(len)) to_add[len]=min(to_add[len],num);
  else to_add[len]=num;

  //update ans
  if(existing.count(k-len)){
    ans=min(ans,existing[k-len]+to_add[len]);
  }

  for(auto p:adj[curr]){
    int to=p.first;
    ll w=p.second;
    if(to==par||rem[to]) continue;
    dfs2(to,curr,num+1,len+w);
  }
}

void build(int curr){
  int n=dfs_sz(curr);
  int c=centroid(curr,-1,n);

  //find paths from c
  existing.clear();
  to_add.clear();
  existing[0]=0;

  for(auto p:adj[c]){
    int to=p.first;
    ll w=p.second;
    if(rem[to]) continue;
    dfs2(to,c,1,w);

    //merge+clear to_add
    for(auto p_:to_add){
      ll len=p_.first;
      int num=p_.second;
      if(existing.count(len)) existing[len]=min(existing[len],num);
      else existing[len]=num;
    }
    to_add.clear();
  }

  //decompose
  rem[c]=true;
  for(auto p:adj[c]){
    int to=p.first;
    if(!rem[to]) build(to);
  }
}

int best_path(int N, int K, int H[][2], int L[])
{
  ans=INF;
  k=K;
  for(int i=0;i<N;i++){
    adj[i].clear();
  }
  for(int i=0;i<N-1;i++){
    int a=H[i][0];
    int b=H[i][1];
    ll w=L[i];
    adj[a].push_back({b,w});
    adj[b].push_back({a,w});
  }
  memset(rem,false,sizeof(rem));

  //centroid decomposition
  build(0);

  return ans==INF?-1:ans;
}

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