Submission #568047

#	Time	Username	Problem	Language	Result	Execution time	Memory
568047		Zanite	Swapping Cities (APIO20_swap)	C++17	100 / 100	1190 ms	50868 KiB

swap

// You can't change other people; you can only change yourself.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#include "swap.h"

// Pragmas
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

// Namespaces
#define yume using
#define wo namespace
#define kanaeyo std
#define nazotte __gnu_pbds
yume wo kanaeyo;
yume wo nazotte;

// Data types
using i8	= __int128;
using ll	= long long;
using si	= short int;
using ld	= long double;

// Pairs
using pi8	= pair<i8, i8>;
using pll	= pair<ll, ll>;
using pii	= pair<int, int>;
using psi	= pair<si, si>;
using pld	= pair<ld, ld>;
#define fi first
#define se second

// PBDS
template<typename T>
using ordered_set	= tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

// Quick macro functions
#define sqr(x) ((x)*(x))
#define pow2(x) (1ll << (x))
#define debug(x) cout << #x << " = " << (x) << '\n'
#define debugV(x, a) cout << #x << "[" << (a) << "] = " << (x[a]) << '\n'

// Check min and max
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
 
// Modular arithmetic
template<typename T> void maddto(T &a, T b, T mod) {a += b; a %= mod;}
template<typename T> void msubto(T &a, T b, T mod) {a -= b; while (a < 0) a += mod; a %= mod;}
template<typename T> void mmulto(T &a, T b, T mod) {a *= b; a %= mod;}
 
template<typename T> T madd(T a, T b, T mod) {a += b; a %= mod; return a;}
template<typename T> T msub(T a, T b, T mod) {a -= b; while (a < 0) a += mod; return a;}
template<typename T> T mmul(T a, T b, T mod) {a *= b; a %= mod; return a;}

// Constants
const ll ModA	= 998244353;
const ll ModC	= 1e9 + 7;
const ll INF	= 1e18;
const ll iINF	= 1e9;
const ld EPS	= 1e-9;
const ld iEPS	= 1e-6;

struct OnlineDSU {
	int n;
	vector<vector<pii>> par, sz, degree, maxdegree, edgecount;

	OnlineDSU(int _n) {
		n = _n;
		for (int i = 0; i < n; i++) {
			par.push_back({{0, i}});
		}
		sz.assign(n, {{0, 1}});
		degree.assign(n, {{0, 0}});
		maxdegree.assign(n, {{0, 0}});
		edgecount.assign(n, {{0, 0}});
	}

	void insert(vector<pii> &v, int val, int t) {
		if (v.back().se == val) {return;}
		if (v.back().fi == t) {
			v.back().se = val;
		} else {
			v.push_back({t, val});
		}
	}

	int query(vector<pii> &v, int t) {
		pii search = {t+1, -iINF};
		auto it = upper_bound(v.begin(), v.end(), search);
		it--;
		return it->second;
	}

	int parent_latest(int x) {return par[x].back().se;}
	int size_latest(int x) {return sz[x].back().se;}
	int degree_latest(int x) {return degree[x].back().se;}
	int maxdegree_latest(int x) {return maxdegree[x].back().se;}
	int edgecount_latest(int x) {return edgecount[x].back().se;}

	int get_degree(int x, int t) {return query(degree[x], t);}
	int get_maxdegree(int x, int t) {return query(maxdegree[x], t);}
	int get_edgecount(int x, int t) {return query(edgecount[x], t);}
	int get_size(int x, int t) {return query(sz[x], t);}

	int rep_latest(int x, int t) {
		if (x == parent_latest(x)) {return x;}
		insert(par[x], rep_latest(parent_latest(x), t), t);
		return parent_latest(x);
	}

	int rep(int x, int t) {
		int p = query(par[x], t);
		if (x == p) {return x;}
		return rep(p, t);
	}

	void join_latest(int u, int v, int t) {
		insert(degree[u], degree_latest(u)+1, t);
		insert(degree[v], degree_latest(v)+1, t);

		int x = rep_latest(u, t), y = rep_latest(v, t);
		if (x != y) {
			if (size_latest(x) < size_latest(y)) {swap(x, y);}

			insert(par[y], x, t);
			insert(sz[x], size_latest(x) + size_latest(y), t);

			int mx = maxdegree_latest(x), my = maxdegree_latest(y);
			insert(maxdegree[x], max(max(mx, my), max(degree_latest(u), degree_latest(v))), t);

			int ex = edgecount_latest(x), ey = edgecount_latest(y);
			insert(edgecount[x], ex+ey+1, t);
		} else {
			insert(maxdegree[x], max(maxdegree_latest(x), max(degree_latest(u), degree_latest(v))), t);
			int e = edgecount_latest(x);
			insert(edgecount[x], e+1, t);
		}
	}

	bool check(int u, int v, int t) {
		int x = rep(u, t), y = rep(v, t);
		return (x == y);
	}
};

void print(vector<vector<pii>> &v) {
	for (int i = 0; i < v.size(); i++) {
		cout << i << ": ";
		for (auto j : v[i]) {
			cout << "{" << j.fi << ", " << j.se << "} ";
		}
		cout << '\n';
	}
	cout << '\n';
}

using Edge	= pair<int, pii>;

OnlineDSU *D;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	vector<Edge> E;
	for (int i = 0; i < M; i++) {
		E.push_back({W[i], {U[i], V[i]}});
	}
	sort(E.begin(), E.end());

	D = new OnlineDSU(N);
	for (auto x : E) {
		D->join_latest(x.se.fi, x.se.se, x.fi);
		//printf("%d: %d %d\n", x.fi, x.se.fi, x.se.se);
	}

	/*
	cout << "par\n";
	print(D->par);
	cout << "sz\n";
	print(D->sz);
	cout << "degree\n";
	print(D->degree);
	cout << "maxdegree\n";
	print(D->maxdegree);
	cout << "edgecount\n";
	print(D->edgecount);
	*/
}

const int MAX = 1e9;

int getMinimumFuelCapacity(int X, int Y) {
	int L = 1, R = MAX, ans = -1;
	while (L <= R) {
		int M = (L + R) >> 1;

		bool pos = 1;
		if (!D->check(X, Y, M)) {
			pos = 0;
		} else {
			int R = D->rep(X, M);
			if (D->get_maxdegree(R, M) > 2 || (D->get_size(R, M) == D->get_edgecount(R, M))) {
				pos = 1;
			} else {
				pos = 0;
			}
		}

		if (pos) {
			R = M - 1;
			ans = M;
		} else {
			L = M + 1;
		}
	}
	return ans;
}

//int main() {}

Compilation message (stderr)

swap.cpp: In function 'void print(std::vector<std::vector<std::pair<int, int> > >&)':
swap.cpp:152:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~

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