Submission #918863

#	Time	Username	Problem	Language	Result	Execution time	Memory
918863		penguin133	Valley (BOI19_valley)	C++17	100 / 100	568 ms	180016 KiB

valley

#include <bits/stdc++.h>
using namespace std;

#define int __int128
typedef long long ll;
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll n, s, q, e;
int S[300005], E[300005], stuf[300050], cnt = 1;
vector <pi> adj[300005];
int U[300005], V[300005], dep[300005], mn[300005], fin[300005], head[300005], up[300005], sz[300005], val[300005], pa[20][200005], f, ans;
pi blk;

void dfs(int x, int p, int d){
	dep[x] = d;
	up[x] = p;
	pa[0][x] = p;
	sz[x] = 1;
	for(auto [i, j] : adj[x]){
		if(i == p)continue;
		dfs(i, x, d + 1);
		sz[x] += sz[i];
	}
}


struct node{
	int s,e,m,val, lazy = 0;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e)>>1;
		val = 0;
		if(s != e)l = new node(s, m), r = new node(m+1, e);
	}
	void propo(){
		if(lazy){
			val += lazy;
			if(s != e)l->lazy += lazy, r->lazy += lazy;
			lazy = 0;
		}
	}
	void upd(int a, int b, int c){
		//cerr << "UPD " << a << " " << b << " " << c << '\n';
		if(a == s && b == e)lazy += c;
		else{
			if(b <= m)l->upd(a, b, c);
			else if(a > m)r->upd(a, b, c);
			else l->upd(a, m, c), r->upd(m+1, b, c);
			l->propo(), r->propo();
			val = min(l->val, r->val);
		}
	}
	int query(int a, int b){
		if(a > b)return 1e18;
		propo();
		if(a == s && b == e)return val;
		else if( b <= m)return l->query(a, b);
		else if(a > m)return r->query(a, b);
		else return min(l->query(a, m), r->query(m+1, b));
	}
}*root, *root2;

void dfs2(int x, int h, int par){
	S[x] = cnt++;
	head[x] = h;
	int maxi = 0, in = -1;
	for(auto [i, j] : adj[x]){
		if(i == par)continue;
		if(maxi < sz[i])maxi = sz[i], in = i;
	}
	for(auto [i, j] : adj[x]){
		if(i == par)continue;
		if(i == in)dfs2(i, h, x);
	}
	for(auto [i, j] : adj[x]){
		if(i != par && i != in)dfs2(i, i, x);
	}
	E[x] = cnt - 1;
}

int query(int a, int b) {
    int res = 1e18;
    for (; head[a] != head[b]; b = up[head[b]]) {
        if (dep[head[a]] > dep[head[b]])
            swap(a, b);
        int cur_heavy_path_max = root->query(S[head[b]], S[b]);
        res = min(res, cur_heavy_path_max);
    }
    if (dep[a] > dep[b])
        swap(a, b);
    res = min(res, root->query(S[a], S[b]));
    return res;
}

//across all parents,
//ans[v] = min(mn[u] - 2 * dep[u]) + dep[v]

void dfs3(int x, int par, int cur){
	val[x] = cur;
	mn[x] = (stuf[x] ? val[x] : 1e18);
	for(auto [i, j] : adj[x]){
		if(i == par)continue;
		dfs3(i, x, cur + j);
		mn[x] = min(mn[x], mn[i]);
	}
}
int cry[300005];
void dfs4(int x, int par){
	if(x == 1)cry[x] = 1e18;
	if(stuf[x])cry[x] = 0;
	multiset <int> ms;
	for(auto [i, j] : adj[x]){
		if(i == par)continue;
		ms.insert(j + mn[i] - val[i]);
	}
	for(auto [i, j] : adj[x]){
		if(i == par)continue;
		ms.erase(ms.find(j + mn[i] - val[i]));
		ms.insert(cry[x]);
		cry[i] = *ms.begin() + j;
		ms.insert(j + mn[i] - val[i]);
		ms.erase(ms.find(cry[x]));
	}
	for(auto [i, j] : adj[x])if(i != par)dfs4(i, x);
}
vector <pii> qu[300005];
int lca(int u, int v){
	if(dep[u] > dep[v])swap(u, v);
	int df = dep[v] - dep[u];
	for(int i = 0; i <= 19; i++)if(df >> i & 1)v = pa[i][v];
	if(u == v)return u;
	for(int i = 19; i >= 0; i--)if(pa[i][u] != pa[i][v])u = pa[i][u], v = pa[i][v];
	return pa[0][u];
}

void solve(){
	cin >> n >> s >> q >> e;
	for(int i = 1; i < n; i++){
		ll a, b, c; cin >> a >> b >> c;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
		U[i] = a, V[i] = b;
	}
	for(int i = 1; i <= s; i++){
		ll x; cin >> x; stuf[x] = 1;
	}
	dfs(1, -1, 1);
	dfs2(1, 1, -1);
	root = new node(1, n);
	root2 = new node(1, n);
	dfs3(1, -1, 0);
	for(int i = 1; i <= 19; i++)for(int j = 1; j <= n; j++)pa[i][j] = pa[i-1][pa[i-1][j]];
	for(int i = 1; i <= n; i++)root->upd(S[i], S[i], mn[i] - 2 * val[i]), root2->upd(S[i], S[i], (stuf[i] ? val[i] : 1e18));
	dfs4(1, -1);
	//for(int i = 1; i <= n; i++)cout << (ll)cry[i] << ' ';
	//cout << '\n';
	for(int i = 1; i <= q; i++){
		ll a, b; cin >> a >> b;
		int tmp = (S[U[a]] < S[V[a]] ? V[a] : U[a]);
		if((S[e] >= S[tmp] && E[e] <= E[tmp]) == (S[b] >= S[tmp] && E[b] <= E[tmp]))fin[i] = -1;
		else {
			if(S[b] >= S[tmp] && E[b] <= E[tmp])fin[i] = query(tmp, b) + val[b];
			else{
				int bruh = lca(tmp, b);
				qu[bruh].push_back({b, {tmp, i}});
				ll df = dep[b] - dep[bruh] - 1;
				df = max(df, 0ll);
				int cur = b;
				for(int j = 19; j >= 0; j--)if(df >> j & 1)cur = pa[j][cur];
				fin[i] = min(cry[bruh] - val[bruh], (b == bruh ? (int)1e18 : query(cur, b))) + val[b];
				//cout << (ll)fin[i] << ' ';
				fin[i] = min(fin[i], min(root2->query(S[bruh], S[tmp] - 1), root2->query(E[tmp] + 1, E[bruh])) - val[bruh] * 2 + val[b]);
			}
		}
	}
	//dfs5(1, -1);
	for(int i = 1; i <= q; i++){
		if(fin[i] == -1)cout << "escaped\n";
		else if(fin[i] >= 1e16)cout << "oo\n";
		else cout << (ll)fin[i] << '\n';
	}
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

valley.cpp:191:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  191 | main(){
      | ^~~~

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41