Submission #585266

#	Time	Username	Problem	Language	Result	Execution time	Memory
585266		vovamr	Swapping Cities (APIO20_swap)	C++17	100 / 100	392 ms	55840 KiB

swap

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "swap.h"
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = 3e5 + 10;

ve<int> gr[N];
int p[N], deg[N], good[N], val[N]; int w = 0;
inline int par(int v) { if (p[v] == v) { return v; } return (p[v] = par(p[v])); }
inline void uni(int a, int b, int we) {
	++deg[a], ++deg[b];
	int pa = par(a), pb = par(b);

	int ok = 0;
	if (deg[a] >= 3) ok = 1;
	if (deg[b] >= 3) ok = 1;

	a = pa, b = pb;
	if (a == b) ok = 1;
	
	int c = w++;

	p[c] = p[a] = p[b] = c;
	val[c] = we, good[c] = ok;

	gr[c].pb(a);
	if (a ^ b) gr[c].pb(b);
}

int tim = 0;
const int lg = 19;

ve<int> eu;
int in[N], out[N], up[N][lg];
inline void dfs(int v, int p) {
	in[v] = sz(eu); eu.pb(v); up[v][0] = p;
	for (auto &to : gr[v]) dfs(to, v);
	out[v] = sz(eu) - 1;
}
inline bool anc(int a, int b) { return in[a] <= in[b] && out[b] <= out[a]; }

int pf[N];

inline int fnd(int a, int b) {
	for (int i = lg - 1; ~i; --i) {
		int u = up[a][i];
		if (!anc(u, b) || pf[out[u]] - (!in[u] ? 0 : pf[in[u] - 1]) == 0) {
			a = u;
		}
	} return up[a][0];
}

void init(int n, int m, ve<int> v1, ve<int> v2, ve<int> we) {
	for (int i = 0; i < n; ++i) p[i] = i, good[i] = 0, deg[i] = 0;
	w = n;

	ve<array<int,3>> e(m);
	for (int i = 0; i < m; ++i) e[i] = {we[i], v1[i], v2[i]};
	sort(all(e));

	for (int i = 0; i < m; ++i) uni(e[i][1], e[i][2], e[i][0]);

	for (int i = 0; i < w; ++i) if (par(i) == i) dfs(i, i);
	for (int i = 1; i < lg; ++i) {
		for (int v = 0; v < w; ++v) {
			up[v][i] = up[up[v][i - 1]][i - 1];
		}
	}
	assert(sz(eu) == w);
	for (int i = 0; i < sz(eu); ++i) pf[i] = good[eu[i]];
	for (int i = 1; i < sz(eu); ++i) pf[i] += pf[i - 1];
}

int getMinimumFuelCapacity(int X, int Y) {
	int ver = fnd(X, Y);
	if (pf[out[ver]] - (!in[ver] ? 0 : pf[in[ver] - 1]) == 0) return -1;
	return val[ver];
}

#ifdef LOCAL
int main() {
  int N, M;
  assert(2 == scanf("%d %d", &N, &M));
  
  std::vector<int> U(M), V(M), W(M);
  for (int i = 0; i < M; ++i) {
    assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
  }

  int Q;
  assert(1 == scanf("%d", &Q));

  std::vector<int> X(Q), Y(Q);
  for (int i = 0; i < Q; ++i) {
    assert(2 == scanf("%d %d", &X[i], &Y[i]));
  }

  init(N, M, U, V, W);
  
  std::vector<int> minimum_fuel_capacities(Q);
  for (int i = 0; i < Q; ++i) {
    minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
  }

  for (int i = 0; i < Q; ++i) {
    printf("%d\n", minimum_fuel_capacities[i]);
  }
  
  return 0;
}
#endif

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