Submission #319939

#	Time	Username	Problem	Language	Result	Execution time	Memory
319939		Blagojce	Swapping Cities (APIO20_swap)	C++11	0 / 100	2094 ms	524292 KiB

swap

#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define rfr(i, n, m) for(int i = (n); i >= (m); i --)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
#include <deque>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int i_inf = 1e9+1;
const ll inf = 2e18;
const ll mod = 998244353;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
const int mxn = 1e5+5;
mt19937 _rand(time(NULL));

#include "swap.h"

vector<pii> g[mxn];
int n, m;
int sparse[mxn][20];
int mis[mxn][20];
int mxw[mxn][20];

int depth[mxn];
int minc[mxn];

int _c[mxn];
int dp[mxn];
void dfs(int u, int p, int val, int val2){
	sparse[u][0] = p;
	fr(i, 1, 20) sparse[u][i] = sparse[sparse[u][i-1]][i-1];
	
	mis[u][0] = val;
	fr(i, 1, 20) mis[u][i] = min(mis[u][i-1], mis[sparse[u][i-1]][i-1]);
	
	mxw[u][0] = val2;
	fr(i, 1, 20) mxw[u][i] = max(mxw[u][i-1], mxw[sparse[u][i-1]][i-1]);
	
	int mi1 = i_inf, c1 = -1;
	int mi2 = i_inf;
	
	for(auto e : g[u]){
		if(e.st == p) continue;
		if(e.nd < mi1){
			mi2 = mi1;
			mi1 = e.nd;
			c1 = e.st;
		}
		else if(e.nd < mi2){
			mi2 = e.nd;
		}
	}
	dp[u] = _c[u];
	for(auto e : g[u]){
		if(e.st == p) continue;
		depth[e.st] = depth[u] + 1;
		if(e.st != c1){
			dfs(e.st, u, mi1, e.nd);
		}
		else{
			dfs(e.st, u, mi2, e.nd);
		}
		dp[u] = min(dp[u], max(dp[e.st], e.nd));
	}
}
int dpup[mxn];
void dfs2(int u, int p, int carry){
	carry = min(carry, _c[u]);
	dpup[u] = carry;
	int id = p;
	int min1 = carry;
	int min2 = i_inf;
	for(auto e : g[u]){
		if(e.st == p) continue;
		int cand1 = max(dp[e.st], e.nd);
		if(cand1 < min1){
			min2 = min1;
			id = e.st;
			min1 = cand1;
		}else if(cand1 < min2){
			min2 = cand1;
		}
	}
	for(auto e : g[u]){
		if(e.st == p) continue;
		if(e.st == id){
			dfs2(e.st, u, max(e.nd, min2));
		}
		else{
			dfs2(e.st, u, max(e.nd, min1));
		}
	}
	

}

int lca(int a, int b){
	int mind = min(depth[a], depth[b]);
	for(int i = 19; i >= 0; i --){
		if(depth[a] - (1<<i) >= mind) a = sparse[a][i];
		if(depth[b] - (1<<i) >= mind) b = sparse[b][i];
	}
	if(a == b) return a;
	
	for(int i = 19; i >= 0; i --){
		if(sparse[a][i] != sparse[b][i]){
			a = sparse[a][i];
			b = sparse[b][i];
		}
	}
	return sparse[a][0];
}
int best_spot(int u, int p){
	int ret = dp[u];
	for(int i = 19; i >= 0; i --){
		if(depth[u] - (1<<i) > depth[p]){
			ret = min(ret, mis[u][i]);
			u = sparse[u][i];
		}
	}
	return ret;
}
int cost(int u, int p){
	int ret = 0;
	for(int i = 19; i >= 0; i --){
		if(depth[u] - (1<<i) >= depth[p]){
			ret = max(ret, mxw[u][i]);
			u = sparse[u][i];
		}
	}
	return ret;
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W){
	n = N, m = M;
	fr(i, 0, m){
		g[U[i]].pb({V[i], W[i]});
		g[V[i]].pb({U[i], W[i]});
	}
	fr(i, 0, n){
		sort(all(g[i]), [](const pii A, const pii B){
			return A.nd < B.nd;
		});
	}
	fr(i, 0, n){
		_c[i] = i_inf;
		if((int)g[i].size() >= 3) _c[i] = g[i][0].nd;
	}
	
	dfs(0, 0, i_inf, i_inf);
	dfs2(0, 0, i_inf);
	fr(i, 0, n){
		minc[i] = i_inf;
		int cnt = 0;
		for(auto u : g[i]){
			if(u.st == sparse[i][0]) continue;
			++cnt;
			if(cnt == 2){
				minc[i] = u.nd;
				break;
			}
		}
	}
	
}
int line = 0;
int getMinimumFuelCapacity(int X, int Y) {
	
	int k = lca(X, Y);
	
	if(X == k){
		int spot = min(best_spot(Y, k), dpup[k]);
		int c = cost(Y, k);
		int tc = max(spot, c);
		if(tc == i_inf) tc = -1;
		
		return tc;
	}
	else if(Y == k){
		int spot = min(best_spot(X, k), dpup[k]);
		int c = cost(X, k);
		int tc = max(spot, c);
		if(tc == i_inf) tc = -1;
		
		return tc;
		
	}
	else{
		int spot = min(min(best_spot(X, k), best_spot(Y, k)), dpup[k]);
		int c1 = cost(X, k);
		int c2 = cost(Y, k);
		int tc = max(spot, max(c1, c2));
		if(tc == i_inf) tc = -1;
		return tc;
	}
}/*
int main(){
	freopen("inp.txt", "r",stdin);
	//freopen("out.txt", "w", stdout);
	cin >> n >> m;
	vector<int> U(m);
	vector<int> V(m);
	vector<int> W(m);

	fr(i, 0, m){
		cin >> U[i] >> V[i] >> W[i];
	}
	
	init(n, m, U, V, W);
	int cc;
	cin >> cc;
	while(cc--){
		int i, j;
		cin >> i >> j;
		++line;
		int ans = getMinimumFuelCapacity(i, j);
		if(line == 1200) cout<<ans<<endl;
	}
	
	


}*/

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