제출 #1104799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1104799		whyalwaysmezzz	Valley (BOI19_valley)	C++17	100 / 100	158 ms	55892 KiB

valley

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define BIT(mask,i) ((mask >> i) & 1ll )
#define endl '\n'  
#define all(x) x.begin(),x.end()
#define ii pair <int,int> 
using namespace std;
template<class X, class Y>bool minimize(X &x, const Y &y) {if (x > y) {x = y;return true;} else return false;}
template<class X, class Y>bool maximize(X &x, const Y &y) {if (x < y) {x = y;return true;} else return false;}
const long long oo = 1e18;
const int N = 1e5+5;
const int MOD = 1e9+7;
vector <ii> g[N];
int h[N];
int p[N][25];
int ns[N][25];
int sum[N];
int n,s,q;
ii ed[N];
int lca(int u,int v)
{
	if (h[u] > h[v]) swap(u,v);
	int gap = h[v] - h[u];
	FOR(k,0,23)
	{
		if (BIT(gap,k))
		{
			v = p[v][k];
		}
	}
	if ( v== u) return u;
	FORD(k,23,0)
	{
		if (p[u][k] != p[v][k])
		{
			u = p[u][k];
			v = p[v][k];
		}
	}
	return p[u][0];
}
void dfs(int u,int par)
{
	h[u] = h[par] + 1;
	p[u][0] = par;
	for(auto [v,w]:g[u])
	{
		if (v == par) continue;
		sum[v] = sum[u] + w;
		dfs(v,u);
		ns[u][0] = min(ns[u][0],ns[v][0] + w);
	}
}
void Whyalwaysmezzz()
{
	int rot;
	cin >> n >> s >> q >> rot;
	FOR(i,1,n-1)
	{
		int u,v,w;
		cin >> u>> v >> w;
		ed[i] = {u,v};
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	FOR(i,1,n) ns[i][0] = oo;
	FOR(i,1,s)
	{
		int lmqzzz;
		cin >> lmqzzz;
		ns[lmqzzz][0] = 0;
	}
	// p[rot][0] = rot;
	dfs(rot,rot);
	FOR(k,1,23)
	{
		FOR(i,1,n) 
		{
			p[i][k] = p[p[i][k-1]][k-1];
			ns[i][k] = min(ns[i][k-1],ns[p[i][k-1]][k-1] + sum[i] - sum[p[i][k-1]]);
		}
	}
	while (q--)
	{
		int x , r;
		cin >> x >> r;
		auto [u,v] = ed[x];
		if (h[u] < h[v]) u = v;
		if (lca(r,u) != u)
		{
			cout << "escaped" << endl;
			continue;
		}
		int gap = h[r] - h[u]+1;
		int ans = oo;
		int tmp = r;
		FOR(k,0,20)
		{
			if (BIT(gap,k))
			{
				int kc = sum[tmp] - sum[r];
				ans = min(ans , kc + ns[r][k]);
				r = p[r][k];
			}
		}
		if (ans >= oo) cout << "oo" << endl;
		else cout << ans << endl;
	}
    return;
}
#define TASK "task"
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);//freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);
    int Sty1e = 1;
    // cin >> Sty1e;
    while (Sty1e--) Whyalwaysmezzz();
    return 0;       
}

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