Submission #303251

#	Time	Username	Problem	Language	Result	Execution time	Memory
303251		nafis_shifat	Swapping Cities (APIO20_swap)	C++14	100 / 100	521 ms	31672 KiB

swap

#include "swap.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int mxn=2e5+1;
const int inf=2e9;
int L[mxn],R[mxn],cost[mxn];



int n,m;
vector<int> sorted;


struct reachability_tree {
	int par[mxn];
	int lineW[mxn];
	int sz[mxn];
	int start[mxn];
	int end[mxn];
	int pw[mxn];

	vector<int> w[mxn];
	vector<int> li[mxn];
	void init(int n) {
		for(int j=0;j<n;j++) {
			sz[j]=1;
			par[j]=j;
			start[j]=j;
		    end[j]=j;
		    lineW[j]=inf;
		}
	}

	int findrep(int u) {
		return par[u]==u ? u : findrep(par[u]);
	}

	void join(int u,int v,int weight) {
		int _u=findrep(u);
		int _v=findrep(v);
		if(_u==_v) {
			lineW[_u]=min(lineW[_u],weight);
			w[_u].push_back(weight);
			li[_u].push_back(lineW[_u]);
			return;
		}

		if(sz[_u]>sz[_v]) {
			swap(_u,_v);
			swap(u,v);
		}

		par[_u]=_v;
		sz[_v]+=sz[_u];
		pw[_u]=weight;

		lineW[_v]=min(lineW[_v],lineW[_u]);
		if(lineW[_v]==inf && ((u==start[_u] || u==end[_u]) && (v==start[_v] || v==end[_v]))) {
			if(v==start[_v]) {
				start[_v]=end[_v];
				end[_v]=start[_u] ^ end[_u] ^ u;
			} else {
				end[_v]=start[_u] ^ end[_u] ^ u;
			}
		} else {
			lineW[_v]=min(lineW[_v],weight);
		}

		w[_v].push_back(weight);
		li[_v].push_back(lineW[_v]);




	}

	int goup(int u,int weight) {

		while(par[u]!=u && pw[u]<=weight) {
			u=par[u];
		}
	
		return u;
	}

	bool check(int x,int weight) {
		int k=upper_bound(w[x].begin(),w[x].end(),weight)-w[x].begin();
		if(k==0) return false;
		int v=li[x][k-1];
		return v<=weight;
	}


} rt;











void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n=N;
	m=M;
	for(int i=0;i<M;i++) {
		L[i]=U[i];
		R[i]=V[i];
		cost[i]=W[i];
		sorted.push_back(i);
		
	}

	sort(sorted.begin(),sorted.end(),[](int a,int b) {
		return cost[a]<cost[b];
	});
	rt.init(n);

	for(int i=0;i<m;i++) {

		int u=L[sorted[i]];
		int v=R[sorted[i]];
		int c=cost[sorted[i]];
		rt.join(u,v,c);

	}

   
}




int getMinimumFuelCapacity(int X, int Y) {

	int lo=0;
	int hi=m-1;
	int ans=-1;
	while(lo<=hi) {
		int m=lo+hi>>1;
		int v=cost[sorted[m]];
		int a=rt.goup(X,v);
		int b=rt.goup(Y,v);
		if(a==b && rt.check(a,v)) {
			ans=v;
			hi=m-1;
		} else {
			lo=m+1;
		}

	}

	return ans;
}

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:144:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  144 |   int m=lo+hi>>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