Submission #605087

#	Time	Username	Problem	Language	Result	Execution time	Memory
605087		daanolav	Race (IOI11_race)	C++14	43 / 100	3062 ms	26992 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;



  ++auxCur;
 
  //cout << "starting cross node for " << treeStart << endl;
  
  auxBest[0] = auxCur;
  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(weight < 0 || weight > k) {
        continue;
      }
      if(auxBest[k - weight] == auxCur) {
        childMin = min(childMin, best[k - weight] + length);
      }
      newResults[weight] = length;
    }
    for(auto& it : newResults) {
      
      if(auxBest[it.first] != auxCur || best[it.first] > it.second) {
        //cout << "added " << it.first << " with " << it.second << " paths" << endl;
        best[it.first] = it.second;
        auxBest[it.first] = auxCur;
      }
    }
  }




  for(ii connection : adjList[centroid]) {
    int adj = connection.first;
    int res = solveFor(adj,centroid);
    //cout << "child " << adj << " res " << res << endl;
    childMin = min(childMin, res);
  }


 
  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: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 0 / 57