Submission #604987

#	Time	Username	Problem	Language	Result	Execution time	Memory
604987		daanolav	Race (IOI11_race)	C++14	21 / 100	3080 ms	26324 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];

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

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

int getCentroid(int node, int parent, int fullSize, unordered_set<int> ignore) {
  
  for(ii connection : adjList[node]) {
    int adj = connection.first;
    if(adj == parent) {
      continue;
    }
    if(ignore.count(adj) == 1) {
      continue;
    }

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

unordered_map<int,int> getPathLengths(int node, int parent, unordered_set<int> ignore) {
  
  unordered_map<int,int> results;
  results[0] = 0;
  for(ii connection : adjList[node]) {
    int adj = connection.first;
    int weight = connection.second;
    if(adj == parent) {
      continue;
    }
    if(ignore.count(adj) == 1) {
      continue;
    }
    
    unordered_map<int,int> sub = getPathLengths(adj,node,ignore);
    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 solveFor(int treeStart, int parent, unordered_set<int> ignore) {
  //cerr << "solveFor " << treeStart << endl;
  if(ignore.count(treeStart) == 1) {
    return 2 * MAXN;
  }
  getSize(treeStart,parent,ignore);
  int centroid = getCentroid(treeStart,parent,treeSize[treeStart],ignore);
  int childMin = MAXN * 2;
  ignore.insert(centroid);
  for(ii connection : adjList[centroid]) {
    int adj = connection.first;
    int res = solveFor(adj,centroid,ignore);
    //cout << "child " << adj << " res " << res << endl;
    childMin = min(childMin, res);
  }

  //cout << "starting cross node for " << treeStart << endl;
  unordered_map<int,int> allResults;
  allResults[0] = 0;
  for(ii connection : adjList[centroid]) {
    int adj = connection.first;
    if(ignore.count(adj) == 1) {
      continue;
    }
    unordered_map<int,int> newResults;
    for(auto& it : getPathLengths(adj,centroid, ignore)) {
      int weight = it.first + connection.second;
      int length = it.second + 1;
      if(allResults.count(k - weight) != 0) {
        childMin = min(childMin, allResults[k - weight] + length);
      }
      newResults[weight] = length;
    }
    for(auto& it : newResults) {
      
      if(allResults.count(it.first) == 0 || allResults[it.first] > it.second) {
        //cout << "added " << it.first << " with " << it.second << " paths" << endl;
        allResults[it.first] = it.second;
      }
    }
  }

  ignore.erase(centroid);

  //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;
  unordered_set<int> ignore;
  int res = solveFor(0,-1,ignore);
  if(res == 2 * MAXN) {
    return -1;
  } else {
    return res;
  }
}

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