제출 #169031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
169031		AlexLuchianov	경주 (Race) (IOI11_race)	C++14	43 / 100	3036 ms	24600 KiB

race

#include "race.h"
#include <vector>
#include <iostream>
#include <algorithm>
#pragma GCC optimize ("O3")

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)
    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)
    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)
    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];
    querynode(e.to, centroid, e.cost, 1, result, k);

    if(seen[e.to] == 0)
      addnode(e.to, centroid, 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, 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]});
  }

  for(int i = 0; i < N; i++)
    std::random_shuffle(g[i].begin(), g[i].end());

  int result = nmax;

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

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'void dfs(int, int)':
race.cpp:25: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:34: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:49: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, int)':
race.cpp:59: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:71: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:84:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[centroid].size(); h++){
                  ~~^~~~~~~~~~~~~~~~~~~~
race.cpp:93:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[centroid].size(); h++){
                  ~~^~~~~~~~~~~~~~~~~~~~
race.cpp:100:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[centroid].size(); h++){
                  ~~^~~~~~~~~~~~~~~~~~~~

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