Submission #291693

#	Time	Username	Problem	Language	Result	Execution time	Memory
291693		nvmdava	Swapping Cities (APIO20_swap)	C++17	100 / 100	431 ms	31768 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int INF = 1000000005;
#define ff first
#define ss second

vector<pair<int, pair<int, int> > > edge;
vector<pair<int, int> > dsu[N];
int ans[N];
int d[N];
vector<int> gr[N];

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	cerr<<"BEGIN";
	for(int i = 0; i < N; ++i)
		ans[i] = INF;
	for(int i = 0; i < N; ++i){
		dsu[i].push_back({0, i});
		gr[i].push_back(i);
	}

	for(int i = 0; i < M; ++i)
		edge.push_back({W[i], {V[i], U[i]}});
	sort(edge.begin(), edge.end());

	for(auto& wtf : edge){
		int v = wtf.ss.ff;
		int u = wtf.ss.ss;
		int w = wtf.ff;

		int vv = dsu[v].back().ss;
		int uu = dsu[u].back().ss;

		if(vv == uu){
			ans[vv] = min(ans[vv], w);
			continue;
		}

		++d[v];
		++d[u];

		if(gr[vv].size() > gr[uu].size()){
			swap(vv, uu);
			swap(v, u);
		}
		ans[uu] = min(ans[uu], max(w, ans[vv]));
		if(d[v] >= 3 || d[u] >= 3){
			ans[uu] = min(ans[uu], w);
		}
		for(auto& x : gr[vv]){
			gr[uu].push_back(x);
			dsu[x].push_back({w, uu});
		}
	}
}

int getMinimumFuelCapacity(int x, int y){
	int ix = dsu[x].size() - 1;
	int iy = dsu[y].size() - 1;
	int w = INF, mn = INF;
	while(ix >= 0 && iy >= 0 && dsu[x][ix].ss == dsu[y][iy].ss){
		w = max(dsu[x][ix].ff, dsu[y][iy].ff);
		mn = min(mn, max(w, ans[dsu[x][ix].ss]));
		--ix; --iy;
	}
	w = max(w, mn);
	return (w == INF ? -1 : w);
}

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