Submission #762079

#	Time	Username	Problem	Language	Result	Execution time	Memory
762079		gun_gan	Race (IOI11_race)	C++17	100 / 100	304 ms	67424 KiB

race

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX = 2e5 + 5;

vector<pair<ll, ll>> g[MX];

int par[MX];
set<pair<ll, ll>> st[MX]; // (total length, num of edge)

ll sum[MX], dep[MX];

int find(int v) {
      return par[v] == v ? v : par[v] = find(par[v]);
}

ll N, K;
ll res = 1e9;

void merge(int u, int v) {
      int tu = u, tv = v;
      u = find(u), v = find(v);

      if(st[u].size() > st[v].size()) {
            swap(u, v);
      }

      par[u] = v;
      for(auto [len, e] : st[u]) {
            // calc answer
            ll k = K - len + 2 * sum[tv];
            auto cur = st[v].lower_bound({k, 0});
            if(cur != st[v].end() && cur->first == k) {
                  res = min(res, e + cur->second - 2 * dep[tv]);
            }
      }

      for(auto [len, e] : st[u]) {
            st[v].insert({len, e});
      }

      st[u].clear();
}

void dfs(int v, int p) {
      for(auto [u, w] : g[v]) {
            if(u == p) continue;
            dep[u] = dep[v] + 1;
            sum[u] = sum[v] + w;
            dfs(u, v);
            merge(u, v);
      }

      find(v);
      // straight line
      auto it = st[par[v]].lower_bound({K + sum[v], 0});
      if(it != st[par[v]].end() && it->first == K + sum[v]) {
            res = min(res, it->second - dep[v]);
      }

      // add path
      st[par[v]].insert({sum[v], dep[v]});
}

int best_path(int n, int k, int h[][2], int w[]) {
      N = n;
      K = k;
      for(int i = 0; i < N - 1; i++) {
            g[h[i][0]].push_back({h[i][1], w[i]});
            g[h[i][1]].push_back({h[i][0], w[i]});
      }

      for(int i = 0; i < N; i++) par[i] = i;

      dfs(0, -1);

      if(res == 1e9) res = -1;
      return res;
}

// int h[MX][2], w[MX];

// int main() {
//       ios_base::sync_with_stdio(0); cin.tie(0);

//       // h[0][0] = 0; h[0][1] = 1;
//       // h[1][0] = 1; h[1][1] = 2;
//       // h[2][0] = 1; h[2][1] = 3;

//       // w[0] = 1;
//       // w[1] = 2;
//       // w[2] = 4;

//       // h[0][0] = 0, h[0][1] = 1;
//       // h[1][0] = 1, h[1][1] = 2;
//       // w[0] = 1;
//       // w[1] = 1;

//       cin >> N >> K;
//       for(int i = 0; i < N - 1; i++) {
//             cin >> h[i][0] >> h[i][1] >> w[i];
//       }
//       // for(int i = 0; i < N - 1; i++) cin >> w[i];

//       cout << best_path(N, K, h, w) << '\n';
// }

Compilation message (stderr)

race.cpp: In function 'void merge(int, int)':
race.cpp:22:11: warning: unused variable 'tu' [-Wunused-variable]
   22 |       int tu = u, tv = v;
      |           ^~

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