제출 #409563

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
409563		600Mihnea	경주 (Race) (IOI11_race)	C++17	100 / 100	457 ms	35768 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;

const int N = 200000 + 7;
const int K = 1000000 + 7;
int last[K], mn[K], event;
int n, k, best, sz[N], total, dist[N];
bool vis[N];
vector<pair<int, int>> g[N];

int get_mn(int x) {
  if (last[x] != event) return N;
  return mn[x];
}

void upd(int x, int val) {
  if (last[x] != event) {
    last[x] = event;
    mn[x] = val;
  } else {
    mn[x] = min(mn[x], val);
  }
}

void build(int a, int p = -1) {
  sz[a] = 1;
  for (auto &edge : g[a]) {
    int b = edge.first, cost = edge.second;
    if (b != p && !vis[b]) {
      build(b, a);
      sz[a] += sz[b];
    }
  }
}

int fcen(int a, int p = -1) {
  int mx = total - sz[a];
  for (auto &edge : g[a]) {
    int b = edge.first, cost = edge.second;
    if (b != p && !vis[b]) {
      mx = max(mx, sz[b]);
    }
  }
  if (mx <= total / 2) {
    return a;
  }
  for (auto &edge : g[a]) {
    int b = edge.first, cost = edge.second;
    if (b != p && !vis[b] && mx == sz[b]) {
      return fcen(b, a);
    }
  }
}

vector<pair<int, int>> dists;

void dfs(int a, int p, int step) {
  if (dist[a] > k) {
    return;
  }
  dists.push_back({dist[a], step});
  for (auto &edge : g[a]) {
    int b = edge.first, cost = edge.second;
    if (b != p && !vis[b]) {
      dist[b] = dist[a] + cost;
      dfs(b, a, step + 1);
    }
  }
}

void solve(int a) {
  build(a);
  total = sz[a];
  a = fcen(a);
  vis[a] = 1;
  event++;
  for (auto &edge : g[a]) {
    int b = edge.first, cost = edge.second;
    if (!vis[b]) {
      dists.clear();
      dist[b] = cost;
      dfs(b, a, 1);
      for (auto &val : dists) {
        int other = k - val.first;
        if (val.first == k) {
          best = min(best, val.second);
        }
        best = min(best, get_mn(other) + val.second);
      }
      for (auto &val : dists) {
        upd(val.first, val.second);
      }
    }
  }
  for (auto &edge : g[a]) {
    int b = edge.first, cost = edge.second;
    if (!vis[b]) {
      solve(b);
    }
  }
}

int best_path(int nodes, int target, int edges[][2], int len_edges[]) {
  best = N;
  n = nodes;
  k = target;
  for (int i = 0; i < n; i++) {
    vis[i] = 0;
    g[i].clear();
  }
  for (int i = 0; i < n - 1; i++) {
    g[edges[i][0]].push_back({edges[i][1], len_edges[i]});
    g[edges[i][1]].push_back({edges[i][0], len_edges[i]});
  }
  solve(0);
  if (best == N) {
    best = -1;
  }
  return best;
}

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

race.cpp: In function 'void build(int, int)':
race.cpp:30:25: warning: unused variable 'cost' [-Wunused-variable]
   30 |     int b = edge.first, cost = edge.second;
      |                         ^~~~
race.cpp: In function 'int fcen(int, int)':
race.cpp:41:25: warning: unused variable 'cost' [-Wunused-variable]
   41 |     int b = edge.first, cost = edge.second;
      |                         ^~~~
race.cpp:50:25: warning: unused variable 'cost' [-Wunused-variable]
   50 |     int b = edge.first, cost = edge.second;
      |                         ^~~~
race.cpp: In function 'void solve(int)':
race.cpp:98:25: warning: unused variable 'cost' [-Wunused-variable]
   98 |     int b = edge.first, cost = edge.second;
      |                         ^~~~
race.cpp: In function 'int fcen(int, int)':
race.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
   55 | }
      | ^

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