Submission #720698

#	Time	Username	Problem	Language	Result	Execution time	Memory
720698		joelgun14	Race (IOI11_race)	C++17	9 / 100	163 ms	41572 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int l;
int res = 1e9;
const int lim = 2e5 + 5;
int depth[lim];
bool vis[lim];
vector<pair<int, int>> edges[lim];
struct disjoint_set {
  int h[lim], sz[lim];
  ll shift[lim];
  // fi -> distance
  // se -> depth
  // cari depth terkecil
  set<pair<int, int>> a[lim];
  disjoint_set() {
    memset(h, -1, sizeof(h));
    memset(sz, 0, sizeof(sz));
    memset(shift, 0, sizeof(shift));
  }
  int fh(int nd) {
    return h[nd] == -1 ? nd : h[nd] = fh(h[nd]);
  }
  bool merge(int x, int y) {
    x = fh(x), y = fh(y);
    if(x != y) {
      if(sz[x] < sz[y])
        swap(x, y);
      sz[x] += sz[y];
      h[y] = x;
      if(a[x].size() < a[y].size()) {
        swap(a[x], a[y]);
      }
      depth[x] = min(depth[x], depth[y]);
      for(auto i : a[y]) {
        // coba cari di a[x] yg panjangnya pas
        int target = l - i.first - shift[x] - shift[y];
        // cari target di a[x];
        if(a[x].lower_bound(make_pair(target, 0)) != a[x].end() && (*a[x].lower_bound(make_pair(target, 0))).first == target) {
          res = min(res, (*a[x].lower_bound(make_pair(target, 0))).second + i.second - 2 * depth[x]);
        }
      }
      for(auto i : a[y]) {
        auto tmp = i;
        tmp.first += shift[y] - shift[x];
        a[x].insert(tmp);
      }
    }
    return x != y;
  }
};

disjoint_set dsu;
void dfs(int nd = 1) {
  vis[nd] = 1;
  dsu.a[nd].insert(make_pair(0, depth[nd]));
  int tmp = depth[nd];
  for(auto i : edges[nd]) {
    if(!vis[i.first]) {
      depth[i.first] = tmp + 1;
      dfs(i.first);
      dsu.shift[dsu.fh(i.first)] += i.second;
      dsu.merge(i.first, nd);
    }
  }
}

int best_path(int N, int K, int H[][2], int L[])
{
  l = K;
  for(int i = 0; i < N - 1; ++i) {
    edges[H[i][0]].push_back(make_pair(H[i][1], L[i]));
    edges[H[i][1]].push_back(make_pair(H[i][0], L[i]));
  }
  dfs();
  if(res == 1e9)
    return -1;
  else
    return res;
}

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