Submission #401665

#	Time	Username	Problem	Language	Result	Execution time	Memory
401665		hoaphat1	Swapping Cities (APIO20_swap)	C++17	37 / 100	2085 ms	14444 KiB

swap

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

struct dsu {
	vector<int> p;
	int n;
	dsu(int n) {
		resize(n);
	}
	dsu() {
	}
	void resize(int _n) {
		n = _n;
		p = vector<int> (n, -1);
	}
	int get(int x) {
		return p[x] < 0 ? x : p[x] = get(p[x]);
	}
	bool unite(int x, int y) {
		x = get(x); y = get(y);
		if (x != y) {
			if (p[x] < p[y]) swap(x, y);
			p[y] += p[x];
			p[x] = y;
			return true;
		}
		return false;
	}
} d;

const int N = 1e5 + 3;
int n, m;
vector<tuple<int,int,int>> edges;
int deg[N];
vector<int> event[N];
bool can[N];

void init(int _n, int _m, vector<int> u, vector<int> v, vector<int> w) {
	n = _n;
	m = _m;
	for (int i = 0; i < m; i++) edges.emplace_back(w[i], u[i], v[i]);
	sort(edges.begin(), edges.end());
	/*d.resize(n);
	for (auto&x : edges) {
		deg[get<1>(x)]++;
		deg[get<2>(x)]++;
		int u = d.get(get<1>(x)), v = d.get(get<2>(x));
		if (u == v) {
			if (!can[u]) {
				event[u].emplace_back(get<0>(x));
				can[u] = true;
			}
		}
		else {
			d.unite(u, v);
			if (u != d.get(u)) swap(u, v);
			
		}
	}*/
}

int getMinimumFuelCapacity(int X, int Y) {
	d.resize(n);
	for (int i = 0; i < n; i++) deg[i] = 0, can[i] = false;
	for (auto&x : edges) {
		++deg[get<1>(x)];
		++deg[get<2>(x)];
		int u = d.get(get<1>(x)), v = d.get(get<2>(x));
		if (u == v) {
			can[u] = true;
		}
		else {
			d.unite(u, v);
			if (u != d.get(u)) swap(u, v);
			can[u] |= can[v];
			if (deg[get<1>(x)] >= 3 || deg[get<2>(x)] >= 3) {
				can[u] = true;
			}
		}
		if (d.get(X) == d.get(Y) && can[d.get(X)]) return get<0>(x);
	}
	return -1;
}

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