Submission #1260680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260680		comgaTramAnh	Race (IOI11_race)	C++20	0 / 100	2 ms	4928 KiB

race

#include "race.h"
#include <iostream>
#include <math.h>
#include <vector>
#include <utility>
int n, k; 
std::vector <std::pair <int, int>> adj[200005]; 
int minDist[1000005]; 
int sizeSubTree[200005];
bool used[200005];  
int ans; 

void dfsSize(int u, int father) {
  sizeSubTree[u] = 1;
  for (int i = 0; i < (int) adj[u].size(); i++) {
    std::pair <int, int> neighbor = adj[u][i];
    if (neighbor.first == father || used[neighbor.first] == true) {
      continue; 
    }
    dfsSize(neighbor.first, u); 
    sizeSubTree[u] += sizeSubTree[neighbor.first]; 
  }
}

int findCentroid(int u, int father, int numbNodes) {
  for (int i = 0; i < (int) adj[u].size(); i++) {
    std::pair <int, int> neighbor = adj[u][i];
    if (neighbor.first == father || used[neighbor.first] == true) {
      continue; 
    }
    if (2 * sizeSubTree[neighbor.first] >= numbNodes) {
      return findCentroid(neighbor.first, u, numbNodes); 
    }
  }
  return u; 
}

void dfs(int u, int father, int numbEdges, int totalLength, bool state) {
  if (totalLength > k) {
    return; 
  }
  if (state == false) {
    ans = std::min(ans, numbEdges + minDist[k - totalLength]); 
  }
  else {
    minDist[totalLength] = std::min(minDist[totalLength], numbEdges); 
  }
  for (int i = 0; i < (int) adj[u].size(); i++) {
    std::pair <int, int> neighbor = adj[u][i];
    if (neighbor.first == father || used[neighbor.first] == true) {
      continue; 
    }
    dfs(neighbor.first, u, numbEdges + 1, totalLength + neighbor.second, state); 
  }
}
     
void centroidDecomposition(int u) {
  dfsSize(u, -1); 
  int centroid = findCentroid(u, -1, sizeSubTree[u]); 
  used[centroid] = true; 
  for (int i = 0; i < (int) adj[centroid].size(); i++) {
    std::pair <int, int> neighbor = adj[centroid][i]; 
    if (used[neighbor.first] == true) {
      continue; 
    }
    dfs(neighbor.first, centroid, 1, neighbor.second, false);
    dfs(neighbor.first, centroid, 1, neighbor.second, true); 
  }
  for (int i = 0; i < (int) adj[centroid].size(); i++) {
    std::pair <int, int> neighbor = adj[centroid][i];
    if (used[neighbor.first] == true) {
      continue; 
    }           
    centroidDecomposition(neighbor.first); 
  }
}

int best_path(int N, int K, int H[][2], int L[])
{
  n = N;
  k = K;
  for (int i = 0; i < N - 1; i++) {
    int u = H[i][0];
    int v = H[i][1]; 
    int length = L[i];  
    adj[u].push_back(std::make_pair(v, length));
    adj[v].push_back(std::make_pair(u, length)); 
  }
  for (int i = 0; i <= K; i++) {
    minDist[i] = N + 5;
  } 
  ans = N + 5; 
  centroidDecomposition(0);
  return (ans == N + 5 ? -1 : ans); 
}  

/*int best_path(int N, int K, std::vector <std::vector <int>> H, std::vector <int> L)
{
  n = N;
  k = K;
  for (int i = 0; i < N - 1; i++) {
    int u = H[i][0];                    
    int v = H[i][1]; 
    int length = L[i];  
    adj[u].push_back(std::make_pair(v, length));
    adj[v].push_back(std::make_pair(u, length)); 
  }
  for (int i = 0; i <= K; i++) {
    minDist[i] = N + 5;
  }
  minDist[0] = 0; 
  ans = N + 5; 
  centroidDecomposition(0);
  return (ans == N + 5 ? -1 : ans); 
}

int main() {
  std::cin >> n >> k; 
  std::vector <std::vector <int>> H(n - 1, std::vector <int>(2, 0)); 
  std::vector <int> L(n - 1, 0);
  for (int i = 0; i < n - 1; i++) {
    std::cin >> H[i][0] >> H[i][1] >> L[i]; 
  }
  std::cout << best_path(n, k, H, L);
  return 0; 
}   */

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