Submission #838749

#	Time	Username	Problem	Language	Result	Execution time	Memory
838749		TonyStark_456	Swapping Cities (APIO20_swap)	C++17	100 / 100	191 ms	34488 KiB

swap

#include<bits/stdc++.h>
#include "swap.h"
#define st first
#define nd second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define pp pop_back
#define mp make_pair
using namespace std;
using pii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vii = vector<pii>;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
	cerr<<h;
	if(sizeof...(t)){
		cerr<<", ";
	}
	debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);
 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
 
const int K=18, N=3e5+5;
int r[N], par[K][N], tim[N], czy[N], deg[N], nxt[N], dep[N];
int find(int v){
	if(r[v]==v)return v;
	return r[v]=find(r[v]);
}
void init(int n, int m, std::vector<int> uu, std::vector<int> vv, std::vector<int> ww) {
	vector<pair<int, pii> > edg;
	for(int i=0; i<m; i++){
		edg.eb(ww[i], mp(uu[i], vv[i]));
	}
	sort(all(edg));
	for(int i=0; i<N; i++){
		r[i]=i;
	}
	int wsk=n;
	for(int ii=0; ii<m; ii++){
		int u=edg[ii].nd.st, v=edg[ii].nd.nd, w=edg[ii].st;
		deg[u]++;
		deg[v]++;
		bool b=(deg[u]>=3||deg[v]>=3);
		u=find(u);
		v=find(v);
		if(u==v && !czy[u]){
			par[0][u]=r[u]=wsk;
			tim[wsk]=w;
			czy[wsk]=1;
			wsk++;
		}
		if(u!=v){
			par[0][u]=r[u]=wsk;
			par[0][v]=r[v]=wsk;
			tim[wsk]=w;
			czy[wsk]=(b||czy[u]||czy[v]);
			wsk++;
		}
	}
	par[0][wsk-1]=wsk-1;
	for(int k=1; k<K; k++){
		for(int i=0; i<wsk; i++){
			par[k][i]=par[k-1][par[k-1][i]];
		}
	}
	for(int i=wsk-1; i>=0; i--){
		if(czy[i])nxt[i]=tim[i];
		else{
			if(par[0][i]==i)nxt[i]=1e9+5;
			else nxt[i]=nxt[par[0][i]];
		}
		if(par[0][i]!=i)dep[i]=dep[par[0][i]]+1;
	}
	for(int i=0; i<wsk; i++){
		//deb(i, par[0][i], czy[i], tim[i], nxt[i], dep[i]);
	}
}
int lca(int u, int v){
	if(dep[u]>dep[v])swap(u, v);
	for(int i=K-1; i>=0; i--){
		if(dep[u]+(1<<i)<=dep[v])v=par[i][v];
	}
	if(u==v)return u;
	for(int i=K-1; i>=0; i--){
		if(par[i][v]!=par[i][u]){
			v=par[i][v];
			u=par[i][u];
		}
	}
	return par[0][u];
}
int getMinimumFuelCapacity(int X, int Y) {
	if(X==Y)return 0;
	int Z=lca(X, Y);
	if(nxt[Z]==1e9+5)return -1;
	else return nxt[Z];
}

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