Submission #426936

#	Time	Username	Problem	Language	Result	Execution time	Memory
426936		nots0fast	Swapping Cities (APIO20_swap)	C++17	100 / 100	512 ms	46996 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp(a) setprecision(a)<<fixed
#define ss second
#define fori(v) for(ll i=0; i<v; i++)
#define forj(v) for(ll j=0; j<v; j++)
#define fork(v) for(ll k=0; k<v; k++)
#define forl(v) for(ll l=0; l<v; l++)
#define fort(v) for(ll t=0; t<v; t++)
#define forz(v) for(ll z=0; z<v; z++)
#define forx(v) for(ll x=0; x<v; x++)
#define fory(v) for(ll y=0; y<v; y++)
#define ll long long
#define ld long double
#define pb(a) push_back(a)
const ll INF = 0x3f3f3f3f;
const ll inf = 1*pow(10,9) + 100;
ll modulo = pow(10,9) + 7;
#define MAX (int)(pow(10,5) + 10)


namespace dsu{
	int aid[MAX];
	vector<int> dsu[MAX];
	vector<pair<int,int> > nodeBelongs[MAX];	// nodes history of components
	int when[MAX];					// when did a component become 2 tracable
	int deg[MAX];					// degree of nodes
	
	
	void init(int n){
		fori(n){
			aid[i] = i, dsu[i].clear(), dsu[i].push_back(i), 
			when[i] = inf, deg[i] = 0, nodeBelongs[i].pb(mp(i, 0));
		}
	}
	
	bool join(int a,int b, int w){  //	1 - if joined, 0 - if they were already joined 
		deg[a]++;
		deg[b]++;
		
		int aid1 = aid[a], aid2 = aid[b];
		
		if(deg[a] > 2 || deg[b] > 2){
			when[aid1] = min(when[aid1], w);
			when[aid2] = min(when[aid2], w);
		}
		
		if(dsu[aid2].size() > dsu[aid1].size())
			swap(aid1,aid2);
		
		if(aid1==aid2){
			when[aid1] = min(when[aid1], w);
			return 0;
		}
		
		if(when[aid2]!=inf && when[aid1] == inf){
			when[aid1] = w;
		}
		
		for(auto hd : dsu[aid2]){
			aid[hd] = aid1;
			dsu[aid1].push_back(hd);
			nodeBelongs[hd].pb(mp(aid1, w));
		}
		dsu[aid2].clear();
		return 1;
	}
};


bool srt(vector<ll>& a, vector<ll>& b){
	return a[2] < b[2];
}



void init(int N, int M,	vector<int> U, vector<int> V, vector<int> W) {
	ll n = N, m = M;
	vector<vector<ll> > edges;
	fori(m){
		ll a = U[i], b = V[i], w = W[i];
		if(a > b){
			swap(a, b);
		}
		edges.pb(vector<ll>({a,b,w}));
	}
	sort(edges.begin(), edges.end(), srt);
	
	set<pair<ll,ll> > seen;
	
	dsu::init(n);
	
	for(auto& el : edges){
		dsu::join(el[0], el[1], el[2]);
	}
}


int getMinimumFuelCapacity(int X, int Y) {
	ll x = X, y = Y;
	if(dsu::when[dsu::aid[x]] == inf ){
		return -1;
	}
	
	ll cmp1 = x, cmp2 = y;
	ll pt1 = 0, pt2 = 0;
	
	int ans = 0;
	while( (cmp1 != cmp2) || (dsu::when[cmp1] == inf) ){
		if(pt1 == (ll)dsu::nodeBelongs[x].size() ){
			cmp2 = dsu::nodeBelongs[y][pt2].ff;
			ans = max(ans, dsu::nodeBelongs[y][pt2].ss);
			++pt2;
		}
		else if(pt2 == (ll)dsu::nodeBelongs[y].size()){
			cmp1 =  dsu::nodeBelongs[x][pt1].ff;
			ans = max(ans, dsu::nodeBelongs[x][pt1].ss);
			++pt1;
		}
		else if(dsu::nodeBelongs[x][pt1].ss <= dsu::nodeBelongs[y][pt2].ss){
			cmp1 =  dsu::nodeBelongs[x][pt1].ff;
			ans = max(ans, dsu::nodeBelongs[x][pt1].ss);
			++pt1;
		}
		else{
			cmp2 = dsu::nodeBelongs[y][pt2].ff;
			ans = max(ans, dsu::nodeBelongs[y][pt2].ss);
			++pt2;
		}
	}
	
	ans = max(ans, dsu::when[cmp1]);
	
	return ans;
}

/*

void deal(){
	int n, m;
	cin>>n>>m;
	vector<int> u(m), v(m), w(m);
	fori(m){
		cin>>u[i];
	}
	fori(m){
		cin>>v[i];
	}
	fori(m){
		cin>>w[i];
	}
	
	init(n, m, u, v, w);
	ll q;
	cin>>q;
	forl(q){
		ll ui, vi;
		cin>>ui>>vi;
		cout<<getMinimumFuelCapacity(ui, vi)<<'\n';
	}
}



int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	deal();
}
*/

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