Submission #605053

#	Time	Username	Problem	Language	Result	Execution time	Memory
605053		daanolav	Race (IOI11_race)	C++14	0 / 100	3 ms	4948 KiB

race

#include "race.h"
#include <bits/stdc++.h>


using namespace std;

typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

#define MAXN 200002


vii adjList[MAXN];
int treeSize[MAXN];
bool ign[MAXN];

int getSize(int node, int parent) {
  int size = 1;
  for(ii connection : adjList[node]) {
    int adj = connection.first;
    if(adj == parent) {
      continue;
    }
    if(ign[adj]) {
      continue;
    }

    size += getSize(adj,node);
  }
  treeSize[node] = size;
  return size;
}

int getCentroid(int node, int parent, int fullSize) {
  
  for(ii connection : adjList[node]) {
    int adj = connection.first;
    if(adj == parent) {
      continue;
    }
    if(ign[adj]) {
      continue;
    }

    if(treeSize[adj] * 2 > fullSize) {
      int res = getCentroid(adj,node,fullSize);
      //cout << "getCentroid(" << node << ") returned " << res << endl;
      return res;
    }
  }
  //cout << node << endl;
  return node;
}

unordered_map<int,int> getPathLengths(int node, int parent,
  int maxValue) {


  unordered_map<int,int> results;
  if(maxValue < 0) {
    return results; 
  }
  results[0] = 0;
  for(ii connection : adjList[node]) {
    int adj = connection.first;
    int weight = connection.second;
    if(adj == parent) {
      continue;
    }
    if(ign[adj]) {
      continue;
    }
    
    unordered_map<int,int> sub = getPathLengths(adj,node, maxValue - weight);
    for(auto& it : sub) {
      int total = weight + it.first;
      if(results.count(total) == 0 || results[total] > (1 + it.second)) {
        results[total] = 1 + it.second;
      }
    }
    
  }

  return results;
}


int k;

int best[1000002];
int auxBest[1000002];
int auxCur = 1;

int solveFor(int treeStart, int parent) {
  //cerr << "solveFor " << treeStart << endl;
  if(ign[treeStart]) {
    return 2 * MAXN;
  }
  getSize(treeStart,parent);
  int centroid = getCentroid(treeStart,parent,treeSize[treeStart]);
  int childMin = MAXN * 2;
  ign[centroid] = true;
  for(ii connection : adjList[centroid]) {
    int adj = connection.first;
    if(ign[adj]) {
      continue;
    }
    int res = solveFor(adj,centroid);
    //cout << "child " << adj << " res " << res << endl;
    childMin = min(childMin, res);
  }

  //cout << "starting cross node for " << treeStart << endl;
  //unordered_map<int,int> allResults;
  ++auxCur;

  int curHere = auxCur;
  //allResults[0] = 0;
  auxBest[0] = curHere;
  best[0] = 0;

  for(ii connection : adjList[centroid]) {
    int adj = connection.first;
    if(ign[adj]) {
      continue;
    }
    unordered_map<int,int> newResults;
    for(auto& it : getPathLengths(adj,centroid,k)) {
      int weight = it.first + connection.second;
      int length = it.second + 1;
      if(auxBest[k - weight] == curHere) {
        childMin = min(childMin, best[k - weight] + length);
      }
      newResults[weight] = length;
    }
    for(auto& it : newResults) {
      
      if(auxBest[it.first] != curHere || best[it.first] > it.second) {
        //cout << "added " << it.first << " with " << it.second << " paths" << endl;
        best[it.first] = it.second;
        auxBest[it.first] = curHere;
      }
    }
  }

  ign[centroid] = false;

  //cerr << "solveFor " << treeStart << " result " << childMin << endl;
  return childMin;



}


int best_path(int N, int K, int H[][2], int L[])
{
  for(int i = 0; i < N - 1; ++i) {
    adjList[H[i][0]].push_back({H[i][1],L[i]});
    adjList[H[i][1]].push_back({H[i][0],L[i]});
  }
  k = K;
  int res = solveFor(0,-1);
  if(res == 2 * MAXN) {
    return -1;
  } else {
    return res;
  }
}

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