Submission #717971

#	Time	Username	Problem	Language	Result	Execution time	Memory
717971		khulegub	경주 (Race) (IOI11_race)	C++14	100 / 100	1224 ms	45772 KiB

race

// Author: Khulegu Batnasan
// Date: 2023-04-03

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

const int MAXN = 1000005;
const int INF = 1000010;
using namespace std;

vector<vector<pair<int, int>>> to;
int n, k;
int ans = INF;
int sz[MAXN];
bool del[MAXN];
// Backlog
map<int, int> dist_min_back;
// <K, V> Save the minimum number of edges with K total length
map<int, int> dist_min;

void calc_size(int u, int pre) {
  sz[u] = 1;
  for (auto [v, w] : to[u]) {
    if (v == pre || del[v]) continue;
    calc_size(v, u);
    sz[u] += sz[v];
  }
}

int find_centroid(int u, int pre, int total) {
  for (auto [v, w] : to[u]) {
    if (v == pre || del[v]) continue;
    if (sz[v] > total / 2) return find_centroid(v, u, total);
  }
  return u;
}

void collect_distances(int u, int pre, int dist, int edges) {
  if (dist_min.count(dist)) {
    dist_min[dist] = min(dist_min[dist], edges);
  } else {
    dist_min[dist] = edges;
  }

  for (auto [v, w] : to[u]) {
    if (v == pre || del[v]) continue;
    collect_distances(v, u, dist + w, edges + 1);
  }
}

void solve_subtree(int u) {
  // Recalculate subtree sizes
  calc_size(u, u);

  // Find the centroid
  int centroid = find_centroid(u, u, sz[u]);

  // Mark the centroid as deleted
  del[centroid] = true;

  dist_min_back.clear();
  dist_min_back[0] = 0;
  
  // Decompose
  for (auto [v, w] : to[centroid]) {
    if (del[v]) continue;
    
    dist_min.clear();

    collect_distances(v, centroid, w, 1);

    // Calculate the answers with backlog
    for (auto [dist, edges] : dist_min) {
      if (dist_min_back.count(k - dist)) {
        int new_ans = dist_min_back[k - dist] + edges;
        ans = min(ans, new_ans);
      }
    }

    // Add to backlog
    for (auto [dist, edges] : dist_min) {
      if (dist_min_back.count(dist)) {
        dist_min_back[dist] = min(dist_min_back[dist], edges);
      } else {
        dist_min_back[dist] = edges;
      }
    }
  }

  // Solve the subtrees
  for (auto [v, w] : to[centroid]) {
    if (del[v]) continue;
    solve_subtree(v);
  }
}

int best_path(int _n, int _k, int H[][2], int L[]) {
  // Given a tree with N vertices with
  // edges H[i][0] and H[i][1] connected
  // And edge lengths L[i].
  // Find a minimum number of edges with
  // their total length equal to exactly K.
  // If no such path exists, return -1.

  n = _n, k = _k;

  to.resize(n);

  for (int i = 0; i < n - 1; i++) {
    int u = H[i][0], v = H[i][1], w = L[i];
    to[u].push_back({v, w});
    to[v].push_back({u, w});
  }

  solve_subtree(0);

  return ans == INF ? -1 : ans;
}

Compilation message (stderr)

race.cpp: In function 'void calc_size(int, int)':
race.cpp:23:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |   for (auto [v, w] : to[u]) {
      |             ^
race.cpp: In function 'int find_centroid(int, int, int)':
race.cpp:31:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |   for (auto [v, w] : to[u]) {
      |             ^
race.cpp: In function 'void collect_distances(int, int, int, int)':
race.cpp:45:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |   for (auto [v, w] : to[u]) {
      |             ^
race.cpp: In function 'void solve_subtree(int)':
race.cpp:65:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |   for (auto [v, w] : to[centroid]) {
      |             ^
race.cpp:73:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |     for (auto [dist, edges] : dist_min) {
      |               ^
race.cpp:81:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |     for (auto [dist, edges] : dist_min) {
      |               ^
race.cpp:91:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |   for (auto [v, w] : to[centroid]) {
      |             ^

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