Submission #333579

#	Time	Username	Problem	Language	Result	Execution time	Memory
333579		alishahali1382	Swapping Cities (APIO20_swap)	C++14	100 / 100	462 ms	42348 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const int mod=1000000007;
const int MAXN=300010, LOG=19;

int n, m;
int par[LOG][MAXN], h[MAXN];
int dsu[MAXN], root[MAXN], deg[MAXN];
bool ok[MAXN];
int W[MAXN], N;

int getpar(int x){ return (dsu[x]==x?x:dsu[x]=getpar(dsu[x]));}

void init(int nn, int mm, vector<int> U, vector<int> V, vector<int> WW){
	iota(dsu, dsu+MAXN, 0);
	iota(root, root+MAXN, 0);
	n=nn;
	m=mm;
	vector<pair<int, pii>> E(m);
	for (int i=0; i<m; i++) E[i]={WW[i], {U[i], V[i]}};
	sort(all(E));
	N=n;
	for (auto p:E){
		int u=p.second.first, v=p.second.second, w=p.first;
		int x=getpar(u), y=getpar(v);
//		debug2(u, v)
//		debug2(x, y)
		
		deg[u]++;
		deg[v]++;
		if (x==y){
			par[0][root[x]]=N;
			root[x]=N;
			ok[N]=1;
			W[N++]=w;
		}
		else{
			par[0][root[x]]=N;
			par[0][root[y]]=N;
			ok[N]=(ok[root[x]]|ok[root[y]]|(deg[u]==3)|(deg[v]==3));
			dsu[y]=x;
			root[x]=N;
			W[N++]=w;
		}
	}
//	for (int i=0; i<N; i++) cerr<<i<<" : "<<W[i]<<" "<<ok[i]<<" "<<par[0][i]<<"\n";
	
	par[0][N-1]=N-1;
	for (int j=1; j<LOG; j++) for (int i=0; i<N; i++) par[j][i]=par[j-1][par[j-1][i]];
	for (int i=N-2; ~i; i--) h[i]=h[par[0][i]]+1;
	
}

int Lca(int x, int y){
	if (h[x]<h[y]) swap(x, y);
	for (int i=0; i<LOG; i++) if ((h[x]-h[y])&(1<<i)) x=par[i][x];
	if (x==y) return x;
	for (int i=LOG-1; ~i; i--) if (par[i][x]!=par[i][y]) x=par[i][x], y=par[i][y];
	return par[0][x];
}

int getMinimumFuelCapacity(int X, int Y){
	if (!ok[N-1]) return -1;
	int V=Lca(X, Y);
	if (ok[V]) return W[V];
	for (int i=LOG-1; ~i; i--) if (!ok[par[i][V]]) V=par[i][V];
	return W[par[0][V]];
}
/*
5 6 
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
1
0 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