Submission #657037

#	Time	Username	Problem	Language	Result	Execution time	Memory
657037		600Mihnea	Swapping Cities (APIO20_swap)	C++17	13 / 100	170 ms	13072 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>

using namespace std;


const int INF = (int) 1e9 + 7;
int n;
int m;
vector<int> t;
vector<int> dim;
vector<int> is_line;
vector<int> is_endpoint;
vector<int> when;
vector<int> when_join;

int root(int a) {
	if (t[a] == a) {
		return t[a];
	} else {
		return root(t[a]);
	}
}

void join(int a, int b, int val) {
	int x = a, y = b;
	a = root(a);
	b = root(b);
	if (a == b) {
		if (is_line[a] == 1) {
			when[a] = val;
		}
		is_line[a] = 0;
		return;
	}
	if (dim[a] < dim[b]) {
		swap(a, b);
		swap(x, y);
	}
	if (is_line[a] && is_line[b] && is_endpoint[x] && is_endpoint[y]) {
		is_line[a] = 1;
		if (dim[a] > 1) {
			is_endpoint[x] = 0;
		}
		if (dim[b] > 1) {
			is_endpoint[y] = 0;
		}
	} else {
		if (is_line[a] == 1) {
			when[a] = val;
			is_line[a] = 0;
		}
	}
	when_join[b] = val; 
	dim[a] += dim[b];
	t[b] = a;
}

void clr() {
	t.resize(n);
	is_line.resize(n);
	is_endpoint.resize(n);
	dim.resize(n);
	when.resize(n);
	when_join.resize(n);
	for (int i = 0; i < n; i++) {
		t[i] = i;
		is_line[i] = 1;
		is_endpoint[i] = 1;
		dim[i] = 1;
		when[i] = -1;
	}
}

struct Edge {
	int a;
	int b;
	int w;
};

bool operator < (Edge first, Edge second) {
	return first.w < second.w;
}

vector<Edge> edges;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n = N;
	m = M;
	assert((int) U.size() == m);
	assert((int) V.size() == m);
	assert((int) W.size() == m);
	
	edges.clear();
	for (int i = 0; i < m; i++) {
		edges.push_back({U[i], V[i], W[i]});
	}
	sort(edges.begin(), edges.end());
	clr();
	for (auto &edge : edges) {
		int a = edge.a;
		int b = edge.b;
		int w = edge.w;
		join(a, b, w);
	}
}



int getMinimumFuelCapacity(int x, int y) {
	if (x == y) {
		return 0;
	}
	vector<int> path_x, path_y;
	while (1) {
		path_x.push_back(x);
		if (x == t[x]) {
			break;
		}
		x = t[x];
	}
	while (1) {
		path_y.push_back(y);
		if (y == t[y]) {
			break;
		}
		y = t[y];
	}
	reverse(path_x.begin(), path_x.end());
	reverse(path_y.begin(), path_y.end());
	bool deja = 0;
	int wjoin = 0;
	for (int i = max((int) path_x.size() - 1, (int) path_y.size() -1); i >= 0; i--) {
		if (i < (int) path_x.size() && i < (int) path_y.size() && path_x[i] == path_y[i]) {
			assert(deja == 0);
			if (deja) {
				return wjoin;
			}
			if (when[path_x[i]] != -1) {
				return max(wjoin, when[path_x[i]]);
			}
		}
		if (i < (int) path_x.size()) {
			if (when[path_x[i]] != -1) deja = 1;
			wjoin = max(wjoin, when_join[path_x[i]]);
		}
		if (i < (int) path_y.size()) {
			if (when[path_y[i]] != -1) deja = 1;
			wjoin = max(wjoin, when_join[path_y[i]]);
		}
	}
	
	return -1;
	exit(0);

	return -1;
	clr();
	for (auto &edge : edges) {
		int a = edge.a;
		int b = edge.b;
		int w = edge.w;
		join(a, b, w);
		//cout << a << " " << b << " | " << w << " and I care about " << x << " " << y << "\n";
		if (root(x) == root(y) && !is_line[root(x)]) {
			return w; 
		}
	}
	return -1;
}

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