Submission #169040

#	Time	Username	Problem	Language	Result	Execution time	Memory
169040		AlexLuchianov	Race (IOI11_race)	C++14	100 / 100	687 ms	34040 KiB

race

#include "race.h"
#include <vector>
#include <iostream>
#include <algorithm>

using ll = long long;

#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 200000;
int const kmax = 1000000;

struct Edge{
  int to;
  int cost;
};
std::vector<Edge> g[1 + nmax];

int sz[1 + nmax], seen[1 + nmax];

void dfs(int node, int parent){
  sz[node] = 1;
  for(int h = 0; h < g[node].size(); h++){
    Edge e = g[node][h];
    if(seen[e.to] == 0 && e.to != parent){
      dfs(e.to, node);
      sz[node] += sz[e.to];
    }
  }
}
 int find_centroid(int node, int parent, int target){
  for(int h = 0; h < g[node].size(); h++){
    Edge e = g[node][h];
    if(e.to != parent && seen[e.to] == 0 && target < sz[e.to])
      return find_centroid(e.to, node, target);
  }
  return node;
}

int dp[1 + kmax];

int stepsadd = 0, stepsdelete = 0, stepsquery = 0;

void addnode(int node, int parent, int acc, int level, int &k){
  if(acc <= k) {
    stepsadd++;
    if(level < dp[acc])
      dp[acc] = level;

    for(int h = 0; h < g[node].size(); h++){
      Edge e = g[node][h];
      if(e.to != parent && seen[e.to] == 0)
        addnode(e.to, node, acc + e.cost, level + 1, k);
    }
  }
}

void deletenode(int node, int parent, int acc, int level, int &k){
  if(acc <= k) {
    stepsdelete++;
    dp[acc] = nmax;
    for(int h = 0; h < g[node].size(); h++){
      Edge e = g[node][h];
      if(e.to != parent && seen[e.to] == 0)
        deletenode(e.to, node, acc + e.cost, level + 1, k);
    }
  }
}

void querynode(int node, int parent, int acc, int level, int &result, int &k){
  if(acc <= k) {
    stepsquery++;
    if(dp[k - acc] + level < result)
      result = dp[k - acc] + level;
    for(int h = 0; h < g[node].size(); h++){
      Edge e = g[node][h];
      if(e.to != parent && seen[e.to] == 0)
        querynode(e.to, node, acc + e.cost, level + 1, result, k);
    }
  }
}

void solve(int node, int &result, int &k){
  dp[0] = 0;

  dfs(node, -1);
  int centroid = find_centroid(node, -1, sz[node] / 2);

  for(int h = 0; h < g[centroid].size(); h++){
    Edge e = g[centroid][h];
    if(seen[e.to] == 0) {
      querynode(e.to, centroid, e.cost, 1, result, k);
      addnode(e.to, centroid, e.cost, 1, k);
    }
  }

  deletenode(centroid, -1, 0, 0, k);

  seen[centroid] = 1;
  for(int h = 0; h < g[centroid].size(); h++){
    Edge e = g[centroid][h];
    if(seen[e.to] == 0)
      solve(e.to, result, k);
  }
}

int best_path(int N, int K, int H[][2], int L[])
{
  for(int i = 0; i <= K; i++)
    dp[i] = nmax;


  for(int i = 0; i < N - 1; i++){
    int x = H[i][0], y = H[i][1];
    g[x].push_back({y, L[i]});
    g[y].push_back({x, L[i]});
  }
  int result = nmax, result2 = 0;

  solve(0, result, K);
  if(result < nmax)
    return result;
  else
    return -1;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
race.cpp: In function 'int find_centroid(int, int, int)':
race.cpp:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
race.cpp: In function 'void addnode(int, int, int, int, int&)':
race.cpp:51:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[node].size(); h++){
                    ~~^~~~~~~~~~~~~~~~
race.cpp: In function 'void deletenode(int, int, int, int, int&)':
race.cpp:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[node].size(); h++){
                    ~~^~~~~~~~~~~~~~~~
race.cpp: In function 'void querynode(int, int, int, int, int&, int&)':
race.cpp:76:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[node].size(); h++){
                    ~~^~~~~~~~~~~~~~~~
race.cpp: In function 'void solve(int, int&, int&)':
race.cpp:90:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[centroid].size(); h++){
                  ~~^~~~~~~~~~~~~~~~~~~~
race.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[centroid].size(); h++){
                  ~~^~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:119:22: warning: unused variable 'result2' [-Wunused-variable]
   int result = nmax, result2 = 0;
                      ^~~~~~~

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