Submission #792887

#	Time	Username	Problem	Language	Result	Execution time	Memory
792887		Trisanu_Das	Swapping Cities (APIO20_swap)	C++17	100 / 100	146 ms	15156 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
 
vector<int> ds, ww1, ww2;
 
int find(int i) { return ds[i] < 0 ? i : find(ds[i]);}
 
void join(int i, int j, int w, int bridge) {
	i = find(i);
	j = find(j);
	if (i == j) ww2[i] = min(ww2[i], w);
	else {
		if (ds[i] > ds[j]) swap(i, j);
		ds[i] += ds[j], ds[j] = i;
		ww1[j] = w;
		ww2[i] = min(ww2[i], max(w, bridge ? 0 : ww2[j]));
	}
}
 
void init(int n, int m, std::vector<int> ii, std::vector<int> jj, std::vector<int> ww) {
	vector<int> hh(m), dd(n);
	for (int i = 0; i < m; i++) hh[i] = i;
	sort(hh.begin(), hh.end(), [&](int i, int j) {return ww[i] < ww[j];});
	ds.assign(n, -1);
	ww1.assign(n, INT_MAX);
	ww2.assign(n, INT_MAX);
	for (int h : hh) {
		dd[ii[h]]++, dd[jj[h]]++;
		join(ii[h], jj[h], ww[h], dd[ii[h]] >= 3 || dd[jj[h]] >= 3);
	}
}
 
int getMinimumFuelCapacity(int i, int j) {
	int w = -1;
	while (i != j) {
		if (ww1[i] < ww1[j]) {
			w = ww1[i];
			i = ds[i];
		} else {
			w = ww1[j];
			j = ds[j];
		}
	}
	while (i >= 0) {
		if (ww2[i] != INT_MAX) return max(w, ww2[i]);
		w = ww1[i];
		i = ds[i];
	}
	return -1;
}

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