Submission #289681

#	Time	Username	Problem	Language	Result	Execution time	Memory
289681		b00n0rp	Swapping Cities (APIO20_swap)	C++17	100 / 100	651 ms	47608 KiB

swap

/*
Soln:
Basically we need to find some 3-degree vertex or a cycle
and we want the minimum value of 
-> max(path from (x,y), path from x to the vertex,(3rd shortest edge or cycle edge))
First compute mst then use dp on tree
dp[u] = best such vertex in subtree of u
dp_par[u] = best such vertex outside subtree of u
*/
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long double LD;
typedef long long ll;
// #define int ll
#define pb push_back
#define mp make_pair
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
typedef map<int,int> mii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
#define F first
#define S second
#define PQ(type) priority_queue<type>
#define PQD(type) priority_queue<type,vector<type>,greater<type> >
#define WL(t) while(t --)
#define SZ(x) ((int)(x).size())
#define runtime() ((double)clock() / CLOCKS_PER_SEC)
#define inrange(i,a,b) ((i>=min(a,b)) && (i<=max(a,b)))

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const int MAXN = 100005;
const int SQRTN = 1003;
const int LOGN = 22;
const double PI=acos(-1);
 
#ifdef int
const int INF=1e16;
#else
const int INF=1e9+5;
#endif
 
const int MOD = 1000000007;
const int FMOD = 998244353;
const double eps = 1e-9;


int n,m;
vpii adj[MAXN];
vpii extra[MAXN];
vector<pair<int,pii> > edges;

int dsusz[MAXN],dsupar[MAXN];

int find(int x){
	if(dsupar[x] == x) return x;
	return dsupar[x] = find(dsupar[x]);
}

void merge(int x,int y,int w){
	int x0 = find(x);
	int y0 = find(y);
	if(x0 == y0){
		extra[x].pb({y,w});
		extra[y].pb({x,w});
		return;
	}
	adj[x].pb({y,w});
	adj[y].pb({x,w});

	if(dsusz[x0] > dsusz[y0]) swap(x0,y0);
	dsupar[x0] = y0;
	dsusz[y0] += dsusz[x0]; 
}

pii par[MAXN][21];
int dep[MAXN],st[MAXN],fin[MAXN];
int dp[MAXN],dp_par[MAXN],val[MAXN];
int tim = 0;

void dfs0(int u,int p,int w,int d){
	val[u] = INF;
	if(extra[u].size()) remin(val[u],extra[u][0].S);
	if(adj[u].size() >= 3) remin(val[u],adj[u][2].S);
	dp[u] = val[u];
	dp_par[u] = val[u];
	st[u] = tim++;
	par[u][0] = {p,w};
	dep[u] = d;
	for(auto v:adj[u]){
		if(v.F != p){
			dfs0(v.F,u,v.S,d+1);
			remin(dp[u],max(v.S,dp[v.F]));
		}
	}
	fin[u] = tim;
}

void dfs_par(int u){
	vpii gg;
	for(auto v:adj[u]){
		if(v.F == par[u][0].F) continue;
		remin(dp_par[v.F],max(v.S,dp_par[u]));
		gg.pb({max(v.S,dp[v.F]),v.S});
	}
	sort(all(gg));
	for(auto v:adj[u]){
		if(v.F == par[u][0].F) continue;
		if(v.F == gg[0].S){
			if(gg.size() != 1){
				remin(dp_par[v.F],max(v.S,gg[1].F));
			}
		}
		else{
			remin(dp_par[v.F],max(v.S,gg[0].F));
		}
		dfs_par(v.F);
	}
}

void init(int N, int M,vi U, vi V, vi W) {
	n = N;
	m = M;
	REP(i,m) edges.pb({W[i],{U[i],V[i]}});
	REP(i,N){
		dsusz[i] = 1;
		dsupar[i] = i;
	}
	sort(all(edges));
	REP(i,m) merge(edges[i].S.F,edges[i].S.S,edges[i].F);
	tim = 0;
	dfs0(1,1,0,0);
	dfs_par(1);
	FOR(j,1,21){
		REP(i,n){
			par[i][j].F = par[par[i][j-1].F][j-1].F;
			par[i][j].S = max(par[i][j-1].S,par[par[i][j-1].F][j-1].S);
		}
	}
}

int lca(int u,int v){
	if(dep[u] < dep[v]) swap(u,v);
	int res = 0;
	FORD(j,20,0){
		if(dep[u]-(1<<j) >= dep[v]){
			remax(res,par[u][j].S);
			u = par[u][j].F;
		}
	}
	if(u == v) return res;
	FORD(j,20,0){
		if(par[u][j].F != par[v][j].F){
			remax(res,par[u][j].S);
			remax(res,par[v][j].S);
			u = par[u][j].F;
			v = par[v][j].F;
		}
	}
	remax(res,par[u][0].S);
	remax(res,par[v][0].S);
	return res;
}

int getMinimumFuelCapacity(int x, int y){
	int ans = lca(x,y);
	remax(ans,min(dp[x],dp_par[x]));
	if(ans >= INF) return -1;
	return ans;	
}

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