Submission #401898

#	Time	Username	Problem	Language	Result	Execution time	Memory
401898		faresbasbs	Swapping Cities (APIO20_swap)	C++14	100 / 100	490 ms	44452 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
vector<pair<int,pair<int,int>>> edges;
set<pair<int,int>> pars[100001];
int par[100001],deg[100001];
vector<int> group[100001];
bool good[100001];

int find(int curr){
	return curr == par[curr] ? curr : par[curr] = find(par[curr]);
}

void merge(int a , int b , int c){
	int p1 = find(a) , p2 = find(b);
	if((good[p2] && !good[p1]) || group[p1].size() < group[p2].size()){
		swap(a,b),swap(p1,p2);
	}
	int pre = good[p1];
	if(good[p1] || good[p2] || deg[a] > 1 || deg[b] > 1){
		good[p1] = 1;
	}
	if(pre == 0 && good[p1]){
		for(auto i : group[p1]){
			pars[i].insert({c,p1});
		}
	}
	deg[a] += 1 , deg[b] += 1;
	for(auto i : group[p2]){
		if(good[p1]){
			pars[i].insert({c,p1});
		}
		group[p1].push_back(i);
		par[i] = p1;
	}
	group[p2].clear();
}

void init(int N , int M , vector<int> U , vector<int> V , vector<int> W){
	for(int i = 0 ; i < N ; i += 1){
		par[i] = i;
		pars[i].insert({0,i});
		group[i] = {i};
	}
	for(int i = 0 ; i < M ; i += 1){
		edges.push_back({W[i],{U[i],V[i]}});
	}
	sort(edges.begin(),edges.end());
	for(auto i : edges){
		int a = i.second.first , b = i.second.second , c = i.first;
		if(find(a) == find(b)){
			if(!good[find(a)]){
				good[find(a)] = 1;
				for(auto j : group[find(a)]){
					pars[j].insert({c,find(a)});
				}
			}
			continue;
		}
		merge(a,b,c);
	}
}

int getMinimumFuelCapacity(int X , int Y){
	for(auto i : pars[X]){
		for(auto j : pars[Y]){
			if(i.second == j.second){
				return max(i.first,j.first);
			}
		}
	}
	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