Submission #1201401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201401		aykhn	Swapping Cities (APIO20_swap)	C++20	100 / 100	1054 ms	49208 KiB

swap

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

using namespace std;

#define inf 0x3F3F3F3F

const int MXN = 1e5 + 5;

vector<array<int, 2>> e[MXN];
vector<array<int, 2>> cnt[4][MXN];

int val(vector<array<int, 2>> &v, int t)
{
  return (*prev(upper_bound(v.begin(), v.end(), array<int, 2>{t, inf})))[1];
}
int get(int x, int t)
{
  int p = val(e[x], t);
  if (p < 0) return x;
  return get(p, t);
}
void inc(int x, int d, int t)
{
  if (d >= 3) return;
  x = get(x, t);
  cnt[d][x].push_back({t, val(cnt[d][x], t) - 1});
  cnt[d + 1][x].push_back({t, val(cnt[d + 1][x], t) + 1});
}
void unite(int x, int y, int t)
{
  x = get(x, t), y = get(y, t);
  if (x == y) return;
  if (val(e[x], t) > val(e[y], t)) swap(x, y);
  e[x][0][1] += e[y][0][1];
  e[y].push_back({t, x});
  for (int i = 0; i < 4; i++) 
  {
    cnt[i][x].push_back({t, val(cnt[i][x], t) + val(cnt[i][y], t)});
  }
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) 
{
  for (int i = 0; i < N; i++)
  {
    e[i] = {{-inf, -1}};
    for (int j = 0; j < 4; j++) cnt[j][i] = {{-inf, 0}};
    cnt[0][i][0][1] = 1;
  }
  vector<array<int, 3>> ed;
  for (int i = 0; i < U.size(); i++) ed.push_back({W[i], U[i], V[i]});
  sort(ed.begin(), ed.end());
  vector<int> deg(N, 0);
  for (auto &[t, u, v] : ed)
  {
    unite(u, v, t);
    inc(u, deg[u]++, t);
    inc(v, deg[v]++, t);
  }
}

int getMinimumFuelCapacity(int X, int Y) 
{
  int l = 0, r = inf;
  while (l < r)
  {
    int mid = (l + r) >> 1;
    if (get(X, mid) != get(Y, mid)) 
    {
      l = mid + 1;
      continue;
    }
    int R = get(X, mid);
    if (val(cnt[1][R], mid) != 2 || val(cnt[3][R], mid)) r = mid;
    else l = mid + 1;
  }
  return (l == inf ? -1 : l);
}

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