Submission #526967

#	Time	Username	Problem	Language	Result	Execution time	Memory
526967		FelipeH	Race (IOI11_race)	C++14	31 / 100	1825 ms	49624 KiB

race

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

const int MAXN = 200000 + 10, MAXK = 1000000 + 10, INF = 100000000;
vector<int> g[MAXN], p[MAXN];
int marc[MAXK], lastSave[MAXK], removed[MAXN], sub[MAXN];
int ans = INF, cnt, globalK;

int debug = 0;

int readMarc(int pos){
  if(pos < 0 || pos > MAXK) return INF;
  if(lastSave[pos] == cnt) return marc[pos];
  else return INF;
}

void writeMarc(int pos, int val){
  marc[pos] = val; lastSave[pos] = cnt;
}

void calcSub(int v, int f){
  sub[v] = 1;
  for(int i = 0;i<(int)g[v].size();i++){
    int viz = g[v][i];
    if(viz == f || removed[viz] == 1) continue;
    calcSub(viz, v);
    sub[v] += sub[viz];
  }
  return;
}

int findCentroid(int v, int f){
  int centroid = v;
  for(int i = 0;i<(int)g[v].size();i++){
    int viz = g[v][i];
    if(removed[viz] == 1 || viz == f) continue;
    if(sub[viz] > sub[v]/2){
      sub[v] -= sub[viz];
      sub[viz] += sub[v];
      centroid = findCentroid(viz, v);
    }
  }
  return centroid;
}

void computeSubtree(int v, int f, int dist, int edgeCount){
  if(dist == globalK){
    ans = min(ans, edgeCount);
    return;
  }
  int possible = readMarc(globalK - dist);
  if(possible != INF){
    ans = min(ans, possible + edgeCount);
  }
  for(int i = 0;i<(int)g[v].size();i++){
    int viz = g[v][i];
    if(viz == f || removed[viz] == 1) continue;
    computeSubtree(viz, v, dist + p[v][i], edgeCount + 1);
  }
  if(dist <= MAXK && readMarc(dist) > edgeCount) writeMarc(dist, edgeCount);
}

void doTree(int v){
  calcSub(v, -1);
  int centroid = findCentroid(v, -1);
  removed[centroid] = 1;
  if(sub[centroid] == 1) return;
  cnt++;
  for(int i = 0;i<(int)g[centroid].size();i++){
    int viz = g[centroid][i];
    if(removed[viz] == 1) continue;
    computeSubtree(viz, centroid, p[centroid][i], 1);
  }
  for(int i = 0;i<(int)g[centroid].size();i++){
    int viz = g[centroid][i];
    if(removed[viz] == 1) continue;
    doTree(viz);
  }
}

int best_path(int N, int K, int H[][2], int L[]){
  globalK = K;
  for(int i = 0;i<N-1;i++){
    int a = H[i][0], b = H[i][1];
    g[a].push_back(b); g[b].push_back(a);
    p[a].push_back(L[i]); p[b].push_back(L[i]);
  }
  calcSub(0,-1);
  doTree(0);
  if(ans == INF) return -1;
  return ans;
}

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