Submission #293419

#	Time	Username	Problem	Language	Result	Execution time	Memory
293419		rama_pang	Swapping Cities (APIO20_swap)	C++14	100 / 100	811 ms	34532 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

class DisjointSet {
 public:
  int n, t = -1;
  vector<vector<pair<int, int>>> p; // (time, data)
  vector<vector<pair<int, int>>> sz;
  vector<vector<pair<int, int>>> deg;
  vector<vector<pair<int, int>>> cycle;

  DisjointSet() {}
  DisjointSet(int n) : n(n), p(n), sz(n), deg(n), cycle(n) {
    for (int i = 0; i < n; i++) {
      p[i].emplace_back(-1, i);
      sz[i].emplace_back(-1, 1);
      deg[i].emplace_back(-1, 0);
      cycle[i].emplace_back(-1, 0);
    }
  }

  int Find(int x) {
    return p[x].back().second == x ? x : Find(p[x].back().second);
  }
  int Unite(int x, int y) {
    t++;
    x = Find(x), y = Find(y);
    if (x != y) {
      if (sz[x].back().second > sz[y].back().second) {
        swap(x, y);
      }
      p[x].emplace_back(t, y);
      sz[y].emplace_back(t, sz[y].back().second + sz[x].back().second);
      if (deg[x].back().second > deg[y].back().second) {
        deg[y].emplace_back(t, deg[x].back().second);
      }
      if (cycle[y].back().second == 0 && cycle[x].back().second == 1) {
        cycle[y].emplace_back(t, 1);
      }
      return 1;
    }
    return 0;
  }
  void UpdateCycle(int x) {
    x = Find(x);
    if (cycle[x].back().second == 0) {
      cycle[x].emplace_back(t, 1);
    }
  }
  void UpdateDegree(int x, int v) {
    x = Find(x);
    if (v > deg[x].back().second) {
      deg[x].emplace_back(t, v);
    }
  }
  int Find(int x, int tt) {
    assert(p[x].size() <= 2);
    int pp = p[x][0].second;
    if (p[x].size() > 1 && p[x][1].first <= tt) {
      pp = p[x][1].second;
    }
    return pp == x ? x : Find(pp, tt);
  }
  int Degree(int x, int tt) {
    int pos = upper_bound(begin(deg[x]), end(deg[x]), make_pair(tt, int(1e9))) - begin(deg[x]) - 1;
    return deg[x][pos].second;
  }
  int Cycle(int x, int tt) {
    int pos = upper_bound(begin(cycle[x]), end(cycle[x]), make_pair(tt, int(1e9))) - begin(cycle[x]) - 1;
    return cycle[x][pos].second;
  }
};

DisjointSet D;
vector<int> values;

bool Check(int x, int y, int m) {
  x = D.Find(x, m), y = D.Find(y, m);
  return x == y && (D.Degree(x, m) >= 3 || D.Cycle(x, m) == 1);
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
  values = W;
  sort(begin(values), end(values));
  vector<array<int, 3>> E;
  for (int i = 0; i < M; i++) {
    E.push_back({W[i], U[i], V[i]});
  }
  sort(begin(E), end(E));
  D = DisjointSet(N);
  for (int i = 0; i < M; i++) {
    static vector<int> deg(N);
    deg[E[i][1]]++, deg[E[i][2]]++;
    if (!D.Unite(E[i][1], E[i][2])) {
      D.UpdateCycle(E[i][1]);
    }
    D.UpdateDegree(E[i][1], min(3, max(deg[E[i][1]], deg[E[i][2]])));
  }
}

int getMinimumFuelCapacity(int X, int Y) {
  int lo = 0, hi = int(values.size()) - 1;
  if (!Check(X, Y, hi)) {
    return -1;
  }
  while (lo < hi) {
    int md = (lo + hi) / 2;
    if (Check(X, Y, md)) {
      hi = md;
    } else {
      lo = md + 1;
    }
  }
  return values[lo];
}

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