Submission #568811

#	Time	Username	Problem	Language	Result	Execution time	Memory
568811		_karan_gandhi	Swapping Cities (APIO20_swap)	C++17	37 / 100	2095 ms	19860 KiB

swap

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

#define ll long long
#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "

template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "[" << p.first << ", " << p.second << "]"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) { cout << "["; for(int i = 0; i < (int)v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) { cin >> p.first; return cin >> p.second; }

struct DSU { // Sorry UFDS
	vector<int> p, s, degree;
	vector<bool> swappable;
	int components;

	void init(int n) {
		p = vector<int>(n);
		iota(all(p), 0);
		s = vector<int>(n, 1);
		swappable = vector<bool>(n, 0);
		degree = vector<int>(n, 0);
		components = n;
	}

	int get(int x) {
		return p[x] = (p[x] == x ? x : get(p[x]));
	}

	void unite(int a, int b) {
		degree[a]++;
		degree[b]++;
		bool _swappable = 0;
		if (degree[a] >= 3 || degree[b] >= 3) _swappable = 1;

		a = get(a);
		b = get(b);

		if (a == b) {
			swappable[a] = 1;
			return;
		}

		if (s[a] > s[b]) swap(a, b);


		p[a] = b;
		s[b] += s[a];
		swappable[b] = (swappable[a] | swappable[b] | _swappable);
		components--;
	}

	bool same_set(int a, int b) {
		return get(a) == get(b);
	}

	int size(int x) {
		return s[get(x)];
	}

	bool is_swappable(int a, int b) {
		return same_set(a, b) && swappable[get(a)] && swappable[get(b)];
	}
};

int n, m;
vector<vector<pair<int, int>>> adj;
vector<pair<int, pair<int, int>>> edges;
int inf = 1e9 + 7;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n = N;
	m = M;
	adj.resize(n);

	for (int i = 0; i < m; i++) {
		adj[U[i]].emplace_back(V[i], W[i]);
		adj[V[i]].emplace_back(U[i], W[i]);
		edges.emplace_back(W[i], make_pair(U[i], V[i]));
	}

	sort(all(edges));
}

int getMinimumFuelCapacity(int x, int y) {
	int ptr = 0;
	DSU dsu;
	dsu.init(n);
	// cout << pl(x) << pl(y) << endl;
	while (!dsu.is_swappable(x, y) && ptr < m) {
		// cout << pl(ptr) << pl(dsu.swappable) << pl(dsu.p) << pl(dsu.degree) << endl;
		// cout << pl(edges[ptr]) << endl;
		dsu.unite(edges[ptr].second.first, edges[ptr].second.second);
		ptr++;
	}
	// cout << pl(ptr) << pl(dsu.swappable) << pl(dsu.p) << pl(dsu.degree) << endl;

	if (!dsu.is_swappable(x, y)) return -1;
	// if (ptr == m && !dsu.swappable[dsu) return -1;

	return edges[ptr - 1].first;
}

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