Submission #319950

#	Time	Username	Problem	Language	Result	Execution time	Memory
319950		Blagojce	Swapping Cities (APIO20_swap)	C++11	36 / 100	601 ms	48020 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 mxw[mxn][20];

int depth[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];
	
	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 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;
}

int link[mxn];
int sz[mxn];
int findx(int x){
	if(x == link[x]) return x;
	link[x] = findx(link[x]);
	return link[x];
}
int secondbest = i_inf;
void unite(int a, int b, int wi){
	int u = a, v = b;
	
	a = findx(a);
	b = findx(b);
	if(a == b){
		secondbest = min(secondbest, wi);
		return;
	}
	if(sz[a] < sz[b]) swap(a, b);
	link[b] = a;
	sz[a] += sz[b];
	g[u].pb({v, wi});
	g[v].pb({u, wi});
	
}
vector<int> G[mxn];
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W){
	n = N, m = M;
	vector<pair<int, pii> > S;
	fr(i, 0, m){
		S.pb({W[i], {U[i], V[i]}});
	}
	sort(all(S));
	fr(i, 0, n){
		link[i] = i;
		sz[i] = 1;
	}
	for(auto edge : S){
		int u = edge.nd.st;
		int v = edge.nd.nd;
		unite(u, v, edge.st);
	}
	fr(i, 0, m){
		G[U[i]].pb(W[i]);
		G[V[i]].pb(W[i]);
	}
	
	fr(i, 0, n){
		sort(all(G[i]));
	}
	fr(i, 0, n){
		_c[i] = i_inf;
		if((int)G[i].size() >= 3) _c[i] = G[i][2];
	}
	
	dfs(0, 0, i_inf, i_inf);
	dfs2(0, 0, i_inf);
	
	
}

	
int line = 0;
int getMinimumFuelCapacity(int X, int Y){
	int k = lca(X, Y);
	
	if(X == k){
		int c = min(secondbest, max(min(dp[k], dpup[k]), cost(Y, k)));
		if(c == i_inf) c = -1;
		return c;
	}
	else if(Y == k){
		int c = min(secondbest, max(min(dp[k], dpup[k]), cost(X, k)));
		if(c == i_inf) c = -1;
		return c;
		
	}
	else{
		int c = min(secondbest, max(min(dp[k], dpup[k]), max(cost(X, k), cost(Y, k))));
		if(c == i_inf) c = -1;
		return c;
	}
}/*
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: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 23 / 23
• Subtask 6: 0 / 27