Submission #299072

#	Time	Username	Problem	Language	Result	Execution time	Memory
299072		erd1	Race (IOI11_race)	C++14	100 / 100	1734 ms	44280 KiB

race

#include "race.h"

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
typedef int64_t lld;
typedef pair<int, int> pii;

/*
struct node;
vector<node*> nodes;
struct node{
  node *L = 0, *R = 0;
  lld l, r, mid;
  int val = 0;
  node(lld ll, lld rr) : l(ll), r(rr), mid((l+r)/2) {}
  node(*node n){ L = n->L, R = n->R, l = n->l, r = n->r, mid = n->mid, val = n->val + 1; }
  node* update(lld x){
    node* n = new node(this);
    if(l == r)return n;
    if(x <= mid){
      if(!n->L) n->L = new node(l, mid);
      return n->L->update(x);
    }else{
      if(!n->R) n->R = new node(mid+1, r);
      return n->R->update(x);
    }
  }
};
*/

vector<vector<pii>> G;

int getSize(int i, int p){
  int sz = 1;
  for(auto x: G[i])if(x.ff != p)sz += getSize(x.ff, i);
  return sz;
}

int getCent(int i, int p, int n){
  int sz = 1; bool fl = true;
  for(auto x : G[i])
    if(x.ff != p){
      auto r = getCent(x.ff, i, n);
      if(r >= 0)return r;
      r = -r;
      if(r > n/2)fl = false;
      sz += r;
    }
  if(n-sz > n/2)fl = false;
  if(fl)return i;
  else return -sz;
}

map<int, int> deps, tdeps;

void dfs(int i, int p, int d, int c){
  if(!deps[d])deps[d] = c;
  else deps[d] = min(deps[d], c);
  for(auto x : G[i])
    if(x.ff != p)
      dfs(x.ff, i, d+x.ss, c+1);
}

int process(int r, int targ){
  //cout << r << endl;
  deps.clear(); tdeps.clear(); tdeps[0] = 1;
  int ans = INT_MAX;
  for(auto x: G[r]){
    G[x.ff].erase(remove(all(G[x.ff]), make_pair(r, x.ss)), G[x.ff].end());
    dfs(x.ff, r, x.ss, 2);
    for(auto i: deps)
      if(tdeps.find(targ-i.ff) != tdeps.end())
        ans = min(ans, tdeps[targ-i.ff]+i.ss-1);
    for(auto i: deps)
      if(!tdeps[i.ff])tdeps[i.ff] = i.ss;
      else tdeps[i.ff] = min(tdeps[i.ff], i.ss);
    deps.clear();
  }
  G[r].resize(0);
  return ans;
}



int best_path(int N, int K, int H[][2], int L[]) {
  G.resize(N);
  for(int i = 0; i < N-1; i++)G[H[i][0]].pb({H[i][1], L[i]}), G[H[i][1]].pb({H[i][0], L[i]});
  int ans = INT_MAX;
  for(int i = 0; i < N; i++)while(G[i].size())ans = min(ans, process(getCent(i, i, getSize(i, i)), K));
  return ans == INT_MAX?-1:(ans-1);
}

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