Submission #169026

#	Time	Username	Problem	Language	Result	Execution time	Memory
169026		AlexLuchianov	Race (IOI11_race)	C++14	0 / 100	6 ms	5112 KiB

race

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

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];

void addnode(int node, int parent, int acc, int level, int k){
  if(acc <= k)
    dp[acc] = MIN(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){
  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);
  }
}

void querynode(int node, int parent, int acc, int level, int &result, int k){
  if(acc <= k)
    result = MIN(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];
    querynode(e.to, 0, e.cost, 1, result, k);

    if(seen[e.to] == 0)
      addnode(e.to, 0, e.cost, 1, k);
  }


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

  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;

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

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:23: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:46: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 deletenode(int, int, int, int)':
race.cpp:55: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 querynode(int, int, int, int, int&, int)':
race.cpp:66: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 solve(int, int&, int)':
race.cpp:78:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[centroid].size(); h++){
                  ~~^~~~~~~~~~~~~~~~~~~~
race.cpp:87:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[centroid].size(); h++){
                  ~~^~~~~~~~~~~~~~~~~~~~
race.cpp:94:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[centroid].size(); h++){
                  ~~^~~~~~~~~~~~~~~~~~~~

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