Submission #1294831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294831		blackscreen1	Valley (BOI19_valley)	C++20	100 / 100	2283 ms	242692 KiB

valley

#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define ld long double
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define iloop_(m, h, g) for (auto i = m; i < h; i += g)
#define jloop_(m, h, g) for (auto j = m; j < h; j += g)
#define kloop_(m, h, g) for (auto k = m; k < h; k += g)
#define lloop_(m, h, g) for (auto l = m; l < h; l += g)
#define getchar_unlocked _getchar_nolock // comment before submission
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define pllll pair<pll, pll>
#define vll vector<ll>
#define qll queue<ll>
#define dll deque<ll>
#define pqll priority_queue<ll>
#define gll greater<ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
ll n, m, q, rt;
ll t1, t2, t3;
vector<pll> adj[100005];
ll sz[100005];
ll vis[100005], par[100005], cdis[100005][20];
ll pre[100005], pos[100005], cnt = 0, unpre[100005];
vector<ll> pres[100005];
void dfs_sz(ll nd, ll pr) {
	sz[nd] = 1;
	for (auto it : adj[nd]) if (vis[it.second] == -1 && it.second != pr) {
		dfs_sz(it.second, nd);
		sz[nd] += sz[it.second];
	}
}
ll fc(ll nd, ll pr, ll cs) {
	for (auto it : adj[nd]) if (vis[it.second] == -1 && it.second != pr && sz[it.second]*2 > cs) return fc(it.second, nd, cs);
	return nd;
}
void dfs_dis(ll nd, ll pr, ll lv, ll cds, ll mnd) {
	pres[mnd].push_back(pre[nd]);
	cdis[nd][lv] = cds;
	for (auto it : adj[nd]) if (vis[it.second] == -1 && it.second != pr) dfs_dis(it.second, nd, lv, cds + it.first, mnd);
}
void construct(ll cnd, ll lv, ll pr) {
	dfs_sz(cnd, -1);
	ll rnd = fc(cnd, -1, sz[cnd]);
	vis[rnd] = lv;
	par[rnd] = pr;
	dfs_dis(rnd, -1, lv, 0, rnd);
	for (auto it : adj[rnd]) if (vis[it.second] == -1) construct(it.second, lv + 1, rnd);
}
struct node {
	ll s, e, m, v = INF;
	node *l, *r;
	node (ll S, ll E) {
		s = S, e = E, m = (S+E)>>1;
		if (s != e) {
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void upd(ll X, ll V) {
		if (s == e) {v = V; return;}
		if (X <= m) l->upd(X, V);
		else r->upd(X, V);
		v = min(l->v, r->v);
	}
	ll qu(ll S, ll E) {
		if (S > E) return INF;
		if (s == S && e == E) return v;
		if (E <= m) return l->qu(S, E);
		if (S > m) return r->qu(S, E);
		return min(l->qu(S, m), r->qu(m+1, E));
	}
} *root[100005];
void dfs_ord(ll nd, ll pr) {
	unpre[cnt] = nd;
	pre[nd] = cnt++;
	for (auto it : adj[nd]) if (it.second != pr) dfs_ord(it.second, nd);
	pos[nd] = cnt - 1;
}
pll edg[100005];
ll cans, id1, id2;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	memset(vis, -1, sizeof(vis));
	cin >> n >> m >> q >> rt;
	rt--;
	iloop(1, n) {
		cin >> t1 >> t2 >> t3;
		t1--, t2--;
		edg[i] = {t1, t2};
		adj[t1].push_back({t3, t2});
		adj[t2].push_back({t3, t1});
	}
	dfs_ord(rt, -1);
	construct(rt, 0, -1);
	iloop(0, n) {
		sort(pres[i].begin(), pres[i].end());
		root[i] = new node(0, pres[i].size() - 1);
	}
	iloop(0, m) {
		cin >> t1;
		t1--;
		t2 = t1;
		while (t1 != -1) {
			root[t1]->upd(lower_bound(pres[t1].begin(), pres[t1].end(), pre[t2]) - pres[t1].begin(), cdis[t2][vis[t1]]);
			t1 = par[t1];
		}
	}
	while (q--) {
		cin >> t1 >> t2;
		t2--;
		if (pre[t2] < max(pre[edg[t1].first], pre[edg[t1].second]) || pre[t2] > min(pos[edg[t1].first], pos[edg[t1].second])) cout << "escaped";
		else {
			cans = INF;
			t3 = t2;
			while (t2 != -1) {
				id1 = lower_bound(pres[t2].begin(), pres[t2].end(), max(pre[edg[t1].first], pre[edg[t1].second])) - pres[t2].begin();
				id2 = upper_bound(pres[t2].begin(), pres[t2].end(), min(pos[edg[t1].first], pos[edg[t1].second])) - pres[t2].begin() - 1;
				cans = min(cans, cdis[t3][vis[t2]] + root[t2]->qu(id1, id2));
				t2 = par[t2];
			}
			if (cans == INF) cout << "oo";
			else cout << cans;
		}
		cout << "\n";
	}
}

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