Submission #485387

#	Time	Username	Problem	Language	Result	Execution time	Memory
485387		lordlorinc	Race (IOI11_race)	C++17	0 / 100	2 ms	4172 KiB

race

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

using namespace std;

int searchedDepth, solution = INT_MAX;
vector<vector<pair<int, int> > > graph;
vector<int> depths, childCount;
vector<bool> visited, disabledNodes;

void calculateChildCount(int pos, int parent){
  childCount[pos] = 1;
  for (pair<int, int> x : graph[pos]){
    if (x.second == parent || disabledNodes[x.second]) continue;
    calculateChildCount(x.second, pos);
    childCount[pos] += childCount[x.second];
  }
}

int findCentroid(int pos, int parent, int maxN){
  int next = -1;
  for (pair<int, int> x : graph[pos]){
    if (x.second == parent || disabledNodes[x.second]) continue;
    if (childCount[x.second] > maxN / 2) next = x.second;
  }
  if (next == -1) return pos;
  else return findCentroid(next, pos, maxN);
}

vector<int> visDepth;
vector<pair<int, int> > curVisNodes;

void calculateDepth (int pos, int parent, int curDepth, int edgeCount){
  curVisNodes.push_back(make_pair(curDepth, edgeCount));
  for (pair<int, int> x : graph[pos]){
    if (x.second == parent || disabledNodes[x.second]) continue;
    calculateDepth (x.second, pos, curDepth + x.first, edgeCount + 1);
  }
}

void solve(int pos){

  // cout << pos << endl;

  calculateChildCount(pos, -1);

  // for (int x : childCount) cout << x << " ";
  // cout << endl;

  pos = findCentroid(pos, -1, childCount[pos]);

  // cout << "pos: " << pos << endl;

  depths[0] = 0;
  for (pair<int, int> x : graph[pos]) {
    if (disabledNodes[x.second]) continue;
    calculateDepth(x.second, pos, x.first, 1);
    
    // cout << "curVisNodes: " << endl;
    // for (pair<int, int> x : curVisNodes) cout << x.first << " " << x.second << endl;
    
    // for (int i = 0; i < 10; i++) cout << depths[i] << " ";
    // cout << endl;

    for (pair<int, int> y : curVisNodes){
      if (y.first <= searchedDepth && depths[searchedDepth - y.first] != -1) {
        // cout << "MEGOLDAS: " << y.first << endl;
        solution = min(solution, y.second + depths[searchedDepth - y.first]);
      }
    }
    for (pair<int, int> y : curVisNodes){
      if (depths[y.first] != -1) {
        depths[y.first] = min(depths[y.first], y.second);
      } 
      else depths[y.first] = y.second;
      visDepth.push_back(x.first);
    }
    curVisNodes.clear();
  }
  for (int x : visDepth) depths[x] = -1;
  visDepth.clear();

  disabledNodes[pos] = true;
  for (pair<int, int> x : graph[pos]){
    if (disabledNodes[x.second] == false) solve(x.second);
  }
}

int best_path(int n, int K, int H[][2], int L[])
{

  searchedDepth = K;
  graph.resize(n);
  disabledNodes.assign(n, false);
  depths.assign(1000000, -1);
  childCount.resize(n);

  for (int i = 0; i < n - 1; i++){
    graph[H[i][0]].push_back(make_pair(L[i], H[i][1]));
    graph[H[i][1]].push_back(make_pair(L[i], H[i][0]));
  }

  // cout << n << " " << K << endl;
  // for (int i = 0; i < n; i++){
  //   for (pair<int, int> y : graph[i]) {
  //     cout << i << " " << y.second << endl;
  //   }
  // }

  solve(0);

  if (solution == INT_MAX) return -1;
  return solution;
}

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