Submission #1134203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134203		finalventure	Race (IOI11_race)	C++17	100 / 100	655 ms	43976 KiB

race

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

using namespace std;

vector<vector<pair<int, int>>> adj;
vector<int> subtree_size;
vector<int> seen;
int total_nodes;
int target_k;
int best_ans = INT_MAX;

int dfs(int node, int par) {
  int sz = 1;
  for (auto [neiDist, neiNode] : adj[node]) {
    if (neiNode == par || seen[neiNode]) continue;
    sz += dfs(neiNode, node);
  }
  return subtree_size[node] = sz;
}

int centroid(int node, int par) {
  for (auto [neiDist, neiNode] : adj[node]) {
    if (neiNode == par || seen[neiNode]) continue;
    if (subtree_size[neiNode] > total_nodes / 2) {
      return centroid(neiNode, node);
    }
  }
  return node;
}

void dfs2(int node, int par, int dist, int edges, unordered_map<int, int>& mp) {
    if (dist > target_k) return;
    if (mp.count(target_k - dist)) {
        best_ans = min(best_ans, edges + mp[target_k - dist]);
    }

    for (auto [neiDist, neiNode] : adj[node]) {
        if (neiNode == par || seen[neiNode]) continue;
        dfs2(neiNode, node, dist + neiDist, edges + 1, mp);
    }
}

void add_to_map(int node, int par, int dist, int edges, unordered_map<int, int>& mp) {
    if (dist > target_k) return;
    if (!mp.count(dist)) {
        mp[dist] = edges;
    } else {
        mp[dist] = min(mp[dist], edges);
    }

    for (auto [neiDist, neiNode] : adj[node]) {
        if (neiNode == par || seen[neiNode]) continue;
        add_to_map(neiNode, node, dist + neiDist, edges + 1, mp);
    }
}


void solve(int node) {
    
  dfs(node, -1);
  total_nodes = subtree_size[node];
  int c = centroid(node, -1);
  seen[c] = 1;

  unordered_map<int, int> mp;
  mp[0] = 0;

  for (auto [neiDist, neiNode] : adj[c]) {
      if (seen[neiNode]) continue;
      unordered_map<int, int> current_mp;
      dfs2(neiNode, c, neiDist, 1, mp);
      add_to_map(neiNode, c, neiDist, 1, mp);
  }

  for (auto [neiDist, neiNode] : adj[c]) {
    if (seen[neiNode]) continue;
    solve(neiNode);
  }
}

int best_path(int N, int K, int H[][2], int L[]) {
  subtree_size.resize(N);
  adj.resize(N);
  seen.resize(N, 0);
  target_k = K;
  for (int i = 0; i < N-1; ++i) {
    adj[H[i][0]].push_back({L[i], H[i][1]});
    adj[H[i][1]].push_back({L[i], H[i][0]});
  }

  solve(0);
    if (best_ans == INT_MAX) {
        return -1;
    }
  return best_ans;
}

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