Submission #530470

#	Time	Username	Problem	Language	Result	Execution time	Memory
530470		hohohaha	Swapping Cities (APIO20_swap)	C++17	13 / 100	139 ms	25356 KiB

swap

#include<bits/stdc++.h>
#include <vector>

using namespace std; 
#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); i++)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); i--) 
#define ii pair<int, int> 
#define fi first
#define se second
#define vi vector<int> 
#define eb emplace_back
#define sp ' '
#define endl '\n'
//#define int long long

const int maxn = 2e5 + 5, inf = INT_MAX / 2; 

int n, m; 
vector<pair<int, ii> > E; 
int deg[maxn]; 
int fre[maxn];
int rt[maxn];
int dep[maxn]; 
int pe[maxn];  
vi cc[maxn]; 

int getrt(int i) { 
	if(rt[i] < 0) return i; 
	return getrt(rt[i]); 
}
void join(int i, int j, int w) { 
	deg[i]++; 
	deg[j]++;
	bool ok = max(deg[i], deg[j]) >= 3;
	i = getrt(i); j = getrt(j); 
//	cout << w << sp << i << sp <<j << "cc" << endl;
	if(i == j) ok = 1; 
	else {
		if(rt[i] > rt[j]) swap(i, j); 
		rt[i] += rt[j]; 
		rt[j] = i; 
		for(int t: cc[j]) cc[i].eb(t); 
		pe[j] = w; 
		dep[j] = dep[i] + 1; 
	}
	if(ok){ 
		for(int x: cc[i]) fre[x] = w; 
		cc[i].clear(); 
	}
}
int get_lca(int u, int v) { 
	if(dep[u] < dep[v]) swap(u, v); 
	int mx = 0; 
	while(dep[u] > dep[v]) {
		mx = max(mx, pe[u]); 
		u = rt[u]; 
	}
	while(u != v) { 
		mx = max(mx, max(pe[u], pe[v])); 
		u = rt[u]; 
		v = rt[v]; 
	}
	return mx; 
}
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = N; 
	m = M;  
	fori(i, 0, m - 1) { 
		int u = U[i] + 1, v = V[i] + 1, w = W[i]; 
		E.eb(make_pair(w, ii(u, v))); 
	}
	sort(begin(E), end(E)); 
	fori(i, 1, n) { 
		fre[i] = inf; 
		rt[i] = -1;  
		pe[i] = -1;
		cc[i].eb(i); 
	}
	for(auto temp: E) { 
		join(temp.se.fi, temp.se.se, temp.fi);
	}
}

int getMinimumFuelCapacity(int X, int Y) {
	int u = X + 1, v = Y + 1; 
//	cout << get_lca(u, v) << endl; 
//	fori(i, 1, n) { 
//		cout << rt[i] << sp << pe[i]  << sp << fre[i] << endl; 
//	}
	int t =  max(get_lca(u, v), min(fre[u], fre[v])); 
	if(t == inf) return -1;
	return t; 
}

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