Submission #553245

#	Time	Username	Problem	Language	Result	Execution time	Memory
553245		FatihSolak	Swapping Cities (APIO20_swap)	C++17	100 / 100	579 ms	47804 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define N 100005
#define M 200005
using namespace std;
vector<pair<int,int>> par[N];
int sz[N];
vector<int> group[N];
vector<pair<int,pair<int,int>>> groupval[N]; 
int ans[M];
int edgecnt;
void init(int n, int m,vector<int> u, vector<int> v, vector<int> w){
	edgecnt = m;
	vector<pair<int,int>> compress;
	for(int i = 0;i<n;i++){
		par[i].push_back({-1,i});
		group[i].push_back(i);
		groupval[i].push_back({-1,{-1,0}});
	}
	for(int i = 0;i<m;i++){
		compress.push_back({w[i],i});
	}
	sort(compress.begin(),compress.end());
	for(int i = 0;i<m;i++){
		ans[i] = compress[i].first;
		int x = compress[i].second;
		if(  group[par[u[x]].back().second].size() > group[par[v[x]].back().second].size()){
			swap(u[x],v[x]);
		}
		sz[u[x]]++;
		sz[v[x]]++;
		int tmp = par[u[x]].back().second;
		//cout << u[x] << " " << v[x] << endl;
		//cout << par[u[x]].back().second << "  a " << par[v[x]].back().second << endl;
		if(par[u[x]].back().second ==  par[v[x]].back().second){
			pair<int,pair<int,int>> nw = {i,{groupval[par[v[x]].back().second].back().second.first + 1,max({groupval[par[v[x]].back().second].back().second.second, groupval[tmp].back().second.second,sz[u[x]],sz[v[x]]})}};
			//cout << nw.second.first << " b " << nw.second.second << endl;
			groupval[par[v[x]].back().second].push_back(nw);
			continue;
		}
		for(auto c:group[tmp]){
			par[c].push_back({i,par[v[x]].back().second});
			group[par[v[x]].back().second].push_back(c);
		}
		pair<int,pair<int,int>> nw = {i,{groupval[par[v[x]].back().second].back().second.first + groupval[tmp].back().second.first + 1,max({groupval[par[v[x]].back().second].back().second.second, groupval[tmp].back().second.second,sz[u[x]],sz[v[x]]})}};
		//cout << nw.second.first << " b " << nw.second.second << endl;
		group[tmp].clear();
		groupval[par[v[x]].back().second].push_back(nw);
		//cout << "hey" << endl;
		//return;
	}
}
bool ck(int x,int y,int val){
	int groupx = prev(lower_bound(par[x].begin(),par[x].end(),make_pair(val+1,-1)))->second;
	int groupy = prev(lower_bound(par[y].begin(),par[y].end(),make_pair(val+1,-1)))->second;
	if(groupx != groupy)
		return 0;
	pair<int,int> tmp = prev(lower_bound(groupval[groupx].begin(),groupval[groupx].end(),make_pair(val+1,make_pair(-1,-1))))->second;
	return (tmp.first > -1) || (tmp.second > 2);
}
int getMinimumFuelCapacity(int x, int y) {
	int l = 0,r = edgecnt;
	while(l < r){
		int m = (l + r)/2;
		if(ck(x,y,m)){
			r = m;
		}
		else l = m+1;
	}
	if(r == edgecnt)return -1;
	return ans[l];
}

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