Submission #1078132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078132		Malix	Race (IOI11_race)	C++14	100 / 100	1399 ms	115008 KiB

race

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

#define REP(a,b,c) for(int a=b;a<c;a++)
#define PB  push_back
#define F first
#define S second
#define LSOne(s) ((s)&(-s))

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;

int inf=1000000010;
int n,k,sv=0,ev=0,m;
vector<pii> a;
vi s,st,en,depth,length,vis;
vii p,b,c;
int ans=inf;

void dfs(int x){
  st[x]=sv++;
  for(auto u:a[x])if(p[x][0]!=u.F){
    p[u.F][0]=x;
    depth[u.F]=depth[x]+1;
    length[u.F]=length[x]+u.S;
    dfs(u.F);
    s[x]+=s[u.F];
  }
  en[x]=ev++;
}

int centroid(int x){
  for(auto u:a[x])if(!vis[u.F]&&s[u.F]>s[x]/2){
    s[x]-=s[u.F];
    s[u.F]+=s[x];
    return centroid(u.F);
  }
  return x;
}

void decompose(int x){
  for(auto u:a[x])if(!vis[u.F]){
    int y=centroid(u.F);
    b[x].PB(y);
    vis[y]=1;
    decompose(y);
  }
}

bool ances(int x,int y){
  if(y==-1)return 1;
  if(st[x]>=st[y]&&en[x]<=en[y])return 1;
  return 0;
}

pi dist(int x,int y){
  if(ances(x,y)||ances(y,x))
    return {abs(depth[x]-depth[y]),abs(length[x]-length[y])};
  int z=y;
  for(int i=m-1;i>=0;i--)if(!ances(x,p[y][i]))y=p[y][i];
  y=p[y][0];
  return {depth[x]+depth[z]-2*depth[y],length[x]+length[z]-2*length[y]};
}

void solve(int x){
  unordered_map<int,int> mp;
  c[x].PB(x);
  for(auto u:b[x]){
    solve(u);
    unordered_map<int,int> tmp;
    for(auto v:c[u]){
      pi r=dist(v,x);
      if(r.S>k)continue;
      if(r.S==k){
        ans=min(ans,r.F);
        continue;
      }
      if(tmp[r.S]==0)tmp[r.S]=r.F;
      else tmp[r.S]=min(tmp[r.S],r.F);
      if(mp[k-r.S]!=0)ans=min(ans,mp[k-r.S]+r.F);
    }
    for(auto v:tmp){
      if(mp[v.F]==0)mp[v.F]=v.S;
      else mp[v.F]=min(mp[v.F],v.S);
    }
    for(auto u:c[u])c[x].PB(u);
  }
}

int best_path(int N, int K, int H[][2], int L[])
{
  n=N;k=K;
  m=log2(n)+2;
  a.resize(n);
  REP(i,0,n-1){
    a[H[i][0]].PB({H[i][1],L[i]});
    a[H[i][1]].PB({H[i][0],L[i]});
  }
  p.resize(n,vi(m,-1));s.resize(n,1);st.resize(n);en.resize(n);
  depth.resize(n,0);length.resize(n,0);vis.resize(n,0);
  vis.resize(n,0);b.resize(n);c.resize(n);
  dfs(0);
  REP(j,1,m)REP(i,0,n)if(p[i][j-1]!=-1)p[i][j]=p[p[i][j-1]][j-1];
  int x=centroid(0);
  vis[x]=1;
  decompose(x);
  solve(x);
  if(ans==inf)return -1;
  return ans;
}

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