Submission #757746

#	Time	Username	Problem	Language	Result	Execution time	Memory
757746		taher	Race (IOI11_race)	C++17	100 / 100	402 ms	44040 KiB

race

#include <bits/stdc++.h>

using namespace std;

const int inf = (int) 1e9;
const int N = (int) 2e5 + 1;
const int M = (int) 1e6 + 1;

vector<pair<int, int>> adj[N];
vector<pair<int, int>> tmp;
int Get_Min[M], idx[M];
int sz[N];
bool vis[N];
int ans = inf;
int k;

int Dfs2(int node, int pre, int depth, int tot, int id) {
  if (tot > k) return inf;
  int res = inf;
  if (idx[k - tot] == id) {
    res = min(res, Get_Min[k - tot] + depth);
  }
  tmp.emplace_back(tot, depth);
  for (auto [x, y] : adj[node]) {
    if (x == pre || vis[x]) {
      continue;
    }
    res = min(res, Dfs2(x, node, depth + 1, tot + y, id));
  }
  return res;
}

int best_path(int n, int K, int edges[][2], int w[]) {
  k = K;
  for (int i = 0; i < n - 1; i++) {
    int a = edges[i][0];
    int b = edges[i][1];
    int c = w[i];

    adj[a].emplace_back(b, c);
    adj[b].emplace_back(a, c);
  }
  int cnt = 0;
  for (int i = 0; i <= k; i++) {
    Get_Min[i] =  inf;
    idx[i] = -1;
  }
  function<int(int, int)> Get_Sub_Sizes = [&](int node, int pre) {  
    sz[node] = 1;
    for (auto [x, y] : adj[node]) {
      if (x == pre || vis[x]) {
        continue;
      }
      sz[node] += Get_Sub_Sizes(x, node);
    }
    return sz[node];
  };

  function<int(int, int, int)> Get_Centroid = [&](int node, int pre, int s) {
    for (auto [x, y] : adj[node]) {
      if (x == pre || vis[x]) {
        continue;
      }
      if (sz[x] > s / 2) {
        return Get_Centroid(x, node, s);
      }
    }
    return node;
  };

  function<void(int, int)> Decompose = [&](int node, int pre) {
    Get_Sub_Sizes(node, pre);
    int c = Get_Centroid(node, pre, sz[node]);
    vis[c] = true;
    Get_Min[0] = 0;
    idx[0] = cnt++;
    for (auto [x, y] : adj[c]) {
      if (x == pre || vis[x]) continue;
      tmp.clear();
      ans = min(ans, Dfs2(x, c, 1, y, idx[0]));
      for (int j = 0; j < (int) tmp.size(); j++) {
        if (idx[tmp[j].first] == idx[0]) {
          Get_Min[tmp[j].first] = min(Get_Min[tmp[j].first], tmp[j].second);  
        }
        else {
          Get_Min[tmp[j].first] = tmp[j].second;
          idx[tmp[j].first] = idx[0];
        }
      }
    }
    for (auto [x, y] : adj[c]) {
      if (vis[x]) {
        continue;
      }
      Decompose(x, c);
    }
  };

  Decompose(0, -1);
  if (ans >= inf) {
    return -1;
  } 
  return ans;
}

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