Submission #762073

#	Time	Username	Problem	Language	Result	Execution time	Memory
762073		gun_gan	Race (IOI11_race)	C++17	9 / 100	111 ms	23188 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(u == v) assert(false);

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

      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]) {
            if(st[v].count({len, e})) continue;

            auto it = st[v].lower_bound({len, 0});
            if(it != st[v].end() && it->first == len) {
                  if(it->second > e) {
                        st[v].erase(it);
                        st[v].insert({len, e});
                  }
            } else {    
                  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);
      }

      for(auto [u, w] : g[v]) {
            if(u == p) continue;

            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);
      assert(res >= 0);
      if(res == 1e9) res = -1;
      return res;
}

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

// 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];
//       }
//       for(int i = 0; i < N - 1; i++) cin >> w[i];

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

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