Submission #848097

#	Time	Username	Problem	Language	Result	Execution time	Memory
848097		comgaTramAnh	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

#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 main () {
  std::cin >> n >> k; 
  for (int i = 1; i < n; i++) {
    int u, v, length;
    std::cin >> u >> v >> length; 
    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); 
  std::cout << (ans == n + 5 ? -1 : ans); 
  return 0; 
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccTF7q0T.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccoIx8FV.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccoIx8FV.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status