제출 #428832

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
428832		Hegdahl	자매 도시 (APIO20_swap)	C++17	13 / 100	491 ms	42120 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define ar array

using namespace std;

const int mxN = 4*2e5;

int deg[mxN], boss[mxN], lk[mxN], rk[mxN], ndw[mxN], can_pass[mxN], nxt;

int find(int i) {
  return i == boss[i] ? i : boss[i] = find(boss[i]);
}

void unite(int i, int j, int w) {
  bool tri = ++deg[i] >= 3 || ++deg[j] >= 3;

  i = find(i), j = find(j);
  if (i == j) {
    if (can_pass[i]) return;
    lk[nxt] = i;
    can_pass[nxt] = 1;
    ndw[nxt] = w;
    boss[i] = nxt++;
    return;
  }

  lk[nxt] = i;
  rk[nxt] = j;
  can_pass[nxt] = tri || can_pass[i] || can_pass[j];
  ndw[nxt] = w;
  boss[i] = boss[j] = nxt++;
}

int up[mxN][20], depth[mxN];
void dfs(int cur, int prv, int d) {
  depth[cur] = d;
  up[cur][0] = prv;
  for (int lvl = 0; lvl < 19; ++lvl)
    up[cur][lvl+1] = up[up[cur][lvl]][lvl];

  if (lk[cur] != -1) dfs(lk[cur], cur, d+1);
  if (rk[cur] != -1) dfs(rk[cur], cur, d+1);
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
  iota(boss, boss+mxN, 0);
  fill(lk, lk+mxN, -1);
  fill(rk, rk+mxN, -1);
  nxt = n;

  vector<int> s(m);
  iota(s.begin(), s.end(), 0);
  sort(s.begin(), s.end(), [&](int i, int j) { return w[i] < w[j]; });
  for (int i : s) unite(u[i], v[i], w[i]);

  for (int i = 1; i < n; ++i)
    assert(find(i) == find(0));

  dfs(find(0), find(0), 0);
}

int getMinimumFuelCapacity(int i, int j) {
  if (depth[i] > depth[j]) swap(i, j);

  for (int lvl = 19; lvl >= 0; --lvl)
    if (depth[up[j][lvl]] >= depth[i])
      j = up[j][lvl];

  for (int lvl = 19; lvl >= 0; --lvl)
    if (up[i][lvl] != up[j][lvl])
      up[i][lvl] = up[j][lvl];

  if (i != j) i = up[i][0], j = up[j][0];

  assert(i == j);

  for (int lvl = 19; lvl >= 0; --lvl)
    if (!can_pass[up[i][lvl]])
      i = up[i][lvl];

  if (!can_pass[i]) i = up[i][0];

  if (!can_pass[i]) return -1;

  return ndw[i];
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27