oj.uz

Submission #918863

# Submission time Handle Problem Language Result Execution time Memory
918863 2024-01-30T15:12:44 Z penguin133 Valley (BOI19_valley) C++17
100 / 100
 568 ms 180016 KB 
#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

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 82776 KB Output is correct
2 Correct 16 ms 82780 KB Output is correct
3 Correct 16 ms 82780 KB Output is correct
4 Correct 17 ms 83036 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 82776 KB Output is correct
2 Correct 16 ms 82780 KB Output is correct
3 Correct 16 ms 82780 KB Output is correct
4 Correct 17 ms 83036 KB Output is correct
5 Correct 15 ms 83180 KB Output is correct
6 Correct 15 ms 83044 KB Output is correct
7 Correct 16 ms 83292 KB Output is correct
8 Correct 16 ms 83108 KB Output is correct
9 Correct 16 ms 83032 KB Output is correct
10 Correct 16 ms 83288 KB Output is correct
11 Correct 16 ms 83288 KB Output is correct
12 Correct 16 ms 83208 KB Output is correct
13 Correct 16 ms 83288 KB Output is correct
14 Correct 16 ms 83288 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 160668 KB Output is correct
2 Correct 377 ms 160476 KB Output is correct
3 Correct 369 ms 160676 KB Output is correct
4 Correct 468 ms 168528 KB Output is correct
5 Correct 387 ms 165324 KB Output is correct
6 Correct 404 ms 180016 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 82776 KB Output is correct
2 Correct 16 ms 82780 KB Output is correct
3 Correct 16 ms 82780 KB Output is correct
4 Correct 17 ms 83036 KB Output is correct
5 Correct 15 ms 83180 KB Output is correct
6 Correct 15 ms 83044 KB Output is correct
7 Correct 16 ms 83292 KB Output is correct
8 Correct 16 ms 83108 KB Output is correct
9 Correct 16 ms 83032 KB Output is correct
10 Correct 16 ms 83288 KB Output is correct
11 Correct 16 ms 83288 KB Output is correct
12 Correct 16 ms 83208 KB Output is correct
13 Correct 16 ms 83288 KB Output is correct
14 Correct 16 ms 83288 KB Output is correct
15 Correct 347 ms 160668 KB Output is correct
16 Correct 377 ms 160476 KB Output is correct
17 Correct 369 ms 160676 KB Output is correct
18 Correct 468 ms 168528 KB Output is correct
19 Correct 387 ms 165324 KB Output is correct
20 Correct 404 ms 180016 KB Output is correct
21 Correct 362 ms 161640 KB Output is correct
22 Correct 356 ms 161144 KB Output is correct
23 Correct 383 ms 161456 KB Output is correct
24 Correct 501 ms 168108 KB Output is correct
25 Correct 397 ms 179208 KB Output is correct
26 Correct 369 ms 162640 KB Output is correct
27 Correct 362 ms 161264 KB Output is correct
28 Correct 410 ms 162728 KB Output is correct
29 Correct 448 ms 169296 KB Output is correct
30 Correct 530 ms 175944 KB Output is correct
31 Correct 343 ms 162384 KB Output is correct
32 Correct 354 ms 161104 KB Output is correct
33 Correct 374 ms 161540 KB Output is correct
34 Correct 464 ms 170320 KB Output is correct
35 Correct 507 ms 179692 KB Output is correct
36 Correct 568 ms 173276 KB Output is correct