Submission #605109

#	Time	Username	Problem	Language	Result	Execution time	Memory
605109		daanolav	Race (IOI11_race)	C++14	100 / 100	411 ms	35240 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;
}


int k;
vii pathLengthResults;
int best[1000002];
int auxBest[1000002];
int auxCur = 1;
 
void getPathLengths(int node, int parent,
  int traveled, int steps) {
 
 
  if(traveled > k) {
    return; 
  }
  pathLengthResults.push_back({traveled,steps});
  for(ii connection : adjList[node]) {
    int adj = connection.first;
    int weight = connection.second;
    if(adj == parent) {
      continue;
    }
    if(ign[adj]) {
      continue;
    }
    
    getPathLengths(adj,node, traveled + weight, steps + 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;

  int weight,length;
  
  auxBest[0] = auxCur;
  for(ii connection : adjList[centroid]) {
    int adj = connection.first;
    if(ign[adj]) {
      continue;
    }
    pathLengthResults.clear();
    getPathLengths(adj,centroid,connection.second,1);
    for(ii path : pathLengthResults) {
      tie(weight,length) = path;
      if(weight < 0 || weight > k) {
        continue;
      }
      if(auxBest[k - weight] == auxCur) {
        childMin = min(childMin, best[k - weight] + length);
      }
    }
    for(ii path : pathLengthResults) {
      tie(weight,length) = path;
      
      if(auxBest[weight] != auxCur || best[weight] > length) {
        //cout << "added " << it.first << " with " << it.second << " paths" << endl;
        best[weight] = length;
        auxBest[weight] = 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: 57 / 57