Submission #319889

#	Time	Username	Problem	Language	Result	Execution time	Memory
319889		Blagojce	Swapping Cities (APIO20_swap)	C++11	0 / 100	2033 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];

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;
		}
	}
	minc[u] = mi1;
	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);
		}
	}
}
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];
}
pii best_spot(int u, int p){
	int ret = i_inf;
	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 {u, 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;
		});
	}
	dfs(0, 0, i_inf, i_inf);
}

int getMinimumFuelCapacity(int X, int Y) {
	
	int k = lca(X, Y);
	if(X == k){
		pii bs = best_spot(Y, k);
		int w1 = bs.nd;
		int spot = w1;
		int c = cost(Y, k);
		int tc = max(spot, c);
		if(tc == i_inf) tc = -1;
		return tc;
	}
	else if(Y == k){
		pii bs = best_spot(X, k);
		int w1 = bs.nd;
		int spot = w1;
		int c = cost(X, k);
		int tc = max(spot, c);
		if(tc == i_inf) tc = -1;
		return tc;
	}
	else{
		pii bs1 = best_spot(X, k);
		pii bs2 = best_spot(Y, k);
		
		int x = bs1.st;
		int w1 = bs1.nd;
		int y = bs2.st;
		int w2 = bs2.nd;
		
		int spot = min(w1, w2);
		
		for(auto u : g[k]){
			if(u.st == x || u.st == y) continue;
			
			spot = min(spot, u.nd);
			break;
		}
		
		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(){
	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;
		cout<<getMinimumFuelCapacity(i, j)<<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