Submission #387771

#	Time	Username	Problem	Language	Result	Execution time	Memory
387771		RohamIzadidoost	Swapping Cities (APIO20_swap)	C++14	30 / 100	771 ms	524292 KiB

swap

#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define SZ(x) (ll)(x).size()
#define X   first
#define Y   second
#define mp  make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
// BIG p : 1000000000000037 , 100000000003
ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 2000*100+5 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1e9 + 7 ;
const int lg = 20 ;
int par[lg][maxn] , sz[maxn] , mark[maxn] , d[maxn]  , flag , ans , dp[maxn] , mx[lg][maxn] , h[maxn] , mo[maxn];
vec<pair<int , pii>> e ;
vec<pii> adj[maxn] ;
void dfsdown(int v , int p){
	for(auto u : adj[v]){
		if(u.X != p ){
			dfsdown(u.X , v) ;
			dp[v] = min(dp[v] , max(dp[u.X] , u.Y)) ;
		}
	}
}
void dfsup(int v , int p){
	for(auto u : adj[v]){
		if(u.X != p){
			dp[u.X] = min(dp[u.X] , max(u.Y , dp[v]))  ; 
			dfsup(u.X , v) ;
		}
	}
}
void dfs(int v , int p){
	for(auto u : adj[v]){
		if(u.X != p){
			par[0][u.X] = v ; 
			mx[0][u.X] = u.Y ; 
			for(int i = 1 ; i < lg; i ++ ){
				par[i][u.X] = par[i-1][par[i-1][u.X]] ; 
				mx[i][u.X] = max(mx[i-1][u.X] , mx[i-1][par[i-1][u.X]]) ;
			} 
			h[u.X] = h[v] + 1 ; 
			dfs(u.X , v) ;
		}
	}
}
int lca(int u , int v){
	int res = 0 ; 
	if(h[u] > h[v]) swap(u , v) ; 
	for(int i = lg-1 ; i >= 0 ; i -- ){
		if(par[i][v] != -1 && h[par[i][v]] >= h[u]){
			res = max(res , mx[i][v]) ;
			v = par[i][v] ; 
		}
	}
	if(u == v) return res ;
	for(int i = lg -1 ; i >= 0 ; i -- ){
		if(par[i][v] != par[i][u]){
			res = max(res , mx[i][v]) ; 
			res = max(res , mx[i][u]) ; 
			u = par[i][u] ; 
			v = par[i][v] ; 
		}
	}
	res = max(res , mx[0][u]) ; res = max(res , mx[0][v]) ; 
	return res ; 
}
int getMinimumFuelCapacity(int x , int y){
	if(max(lca(x , y) , dp[x]) == mod)
	return -1 ; 
	else return max(lca(x , y) , dp[x]) ;
}
void init(int n , int m , vec<int> A , vec<int> B , vec<int> W ){
	for(int i = 0 ; i < m ; i ++ ){
		e.pb({W[i] , {A[i] , B[i]}}) ; 
		adj[A[i]].pb({B[i] , W[i]}) ; 
		adj[B[i]].pb({A[i] , W[i]}) ; 
	}
	sort(all(e)) ;
	for(int i = 0 ; i < maxn ; i ++ ){
		dp[i] = mod ;
	}
	for(auto u : e){
		d[u.Y.X] ++ ; 
		d[u.Y.Y] ++ ; 
		if(d[u.Y.X] == 3) dp[u.Y.X] = u.X ; 
		if(d[u.Y.Y] == 3) dp[u.Y.Y] = u.X ; 
	}
	for(auto u : e){
		dp[u.Y.X] = min(dp[u.Y.X] , max(u.X , dp[u.Y.Y])) ; 
		dp[u.Y.Y] = min(dp[u.Y.Y] , max(u.X , dp[u.Y.X])) ; 
	}
	dfsdown(0 , -1) ;
	dfsup(0 , -1) ;  
	h[0] = 1 ; 
	for(int i  = 0 ; i < lg ; i ++ ) par[i][0] = -1 ;
	dfs(0 , -1) ;
}
/*int main()
{
	migmig ;
	int n , m  ; 
	cin>>n>>m ; 
	int u[m] , v[m] , w[m] ;
	for(int i = 0 ; i < m ; i ++ ) cin>>u[i]>>v[i]>>w[i] ; 
	init(n , m , u , v , w) ;
	int q ; 
	cin>>q ; 
	while(q--){
		int U , V ; 
		cin>>U>>V ; 
		cout<<getMinimumFuelCapacity(U , V) << endl ; 
	}
}*/

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