Submission #978835

#	Time	Username	Problem	Language	Result	Execution time	Memory
978835		kwongweng	Race (IOI11_race)	C++17	100 / 100	413 ms	88432 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef vector<vector<ll>> vll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define ms memset
#define fi first
#define se second

const int mxn = 2e5+1;
vii g[mxn]; vi p(mxn);
map<int,int> S[mxn]; 
int ans;
vector<ll> dist(mxn); // # kilometres from root
vi dist2(mxn); //# highways from root
int k;

//compute distance to root
void dfs1(int u){
  for (ii edge : g[u]){
    int v = edge.fi; int w = edge.se;
    if (p[u]==v) continue;
    p[v] = u; dist[v] = dist[u]+w;
    dist2[v] = dist2[u]+1; dfs1(v);
  }
}

//small to large merging
vi add(mxn); //S[v+add[v]]
void dfs2(int u){
  S[u][0] = u;
  for (ii edge : g[u]){
    int v = edge.fi; int w = edge.se;
    if (p[u]==v) continue;
    dfs2(v);
    add[v]+=w;
    if (S[u].size()<S[v].size()) {swap(S[u],S[v]); swap(add[u],add[v]);}
    for (auto d : S[v]){
      int D = d.fi + add[v] + add[u];
      //if (D > k+2e6) continue;
      if (S[u].find(k-D) != S[u].end()){
        int v1 = S[u][k-D], v2 = d.se;
        //cout<<"Candidates "<<v1<<" "<<v2<<"\n";
        ans = min(ans, dist2[v1] + dist2[v2] - 2*dist2[u]);
      }
    }
    for (auto d : S[v]){
      int D = d.fi + add[v] - add[u];
      //if (D > k+2e6) continue;
      if (S[u].find(D) != S[u].end()){
        int v1 = S[u][D]; int v2 = d.se;
        if (dist2[v2] < dist2[v1]) S[u][D] = v2;
      }else{
        S[u][D] = d.se;
      }
    }
  }
  /*
  cout<<u<<"add " << add[u] <<"\n";
  for (auto d : S[u]){
    cout<<d.fi<<" "<<d.se<<"\n";
  }
  */
}

int best_path(int N, int K, int H[][2], int L[])
{
  k = K;
  ans = N;
  FOR(i,0,N-1){
    g[H[i][0]].pb({H[i][1],L[i]});
    g[H[i][1]].pb({H[i][0],L[i]});
  } 
  dfs1(0); dfs2(0);
  if (ans==N) ans = -1;
  return ans;
}

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