Submission #762059

#	Time	Username	Problem	Language	Result	Execution time	Memory
762059		gun_gan	Race (IOI11_race)	C++17	0 / 100	6 ms	14420 KiB

race

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

const int MX = 2e5 + 5;

vector<pair<int, int>> 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]);
}

int N, K;
ll res = 1e9;

void merge(int u, int v, int p) {
      u = find(u), v = find(v);
      if(u == v) return;

      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[p];
            auto cur = st[v].lower_bound({k, 0});
            if(cur != st[v].end() && cur->first == k) {
                  res = min(res, e + cur->second - 2 * dep[p]);
            }
      }

      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, p);
      }

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

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

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, N);
      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: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57