Submission #493035

#	Time	Username	Problem	Language	Result	Execution time	Memory
493035		Haruto810198	Valley (BOI19_valley)	C++17	100 / 100	937 ms	116836 KiB

valley

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 100010;

// in
int n, q;
int root;
int shops;

int eu[MAX], ev[MAX], ew[MAX]; // i-th edge = (eu[i], ev[i])
vector<pii> edge[MAX]; // to, dis
bool isshop[MAX];

// HLD
int sz[MAX], par[MAX], dep[MAX], fr[MAX], heavy[MAX], id[MAX], from[MAX], to[MAX];
int ts = 1, ets;

// sweep line
int dp[MAX];
vector<vi> EV;
// modify : time, insert/erase, val
// query  : time, 2

// sparse table
int st[MAX][20];

// res = min(dep[shop] - 2*dep[lca]) + dep[qv]

void find_sz(int v, int pv){
	// find sz, par, dep, heavy
	
	par[v] = pv;
	sz[v] = 1;
	from[v] = ets++;

	int Max = 0;
	heavy[v] = -1;
	for(pii e : edge[v]){
		int i = e.F, dd = e.S;
		if(i == pv) continue;
		
		dep[i] = dep[v] + dd;
		find_sz(i, v);
		sz[v] += sz[i];
		
		if(sz[i] > Max){
			Max = sz[i];
			heavy[v] = i;
		}
	}

	to[v] = ets++;
	
}

void HLD(int v, int pv, int frv){
	// HLD subtree v
	fr[v] = frv;
	id[v] = ts++;
	
	if(heavy[v] != -1) HLD(heavy[v], v, frv);
	
	for(pii e : edge[v]){
		int i = e.F;
		if(i == pv or i == heavy[v]) continue;
		HLD(i, v, i);
	}
}

void add_seg(int v){
	int val = dep[v];
	while(v != root){
		// node id : [fr[v], v]
		// st   id : [id[fr[v]], id[v]]
		EV.pb({id[fr[v]], 1, val});
		EV.pb({id[v] + 1, -1, val});
		v = par[fr[v]];
	}
	
	// v == root
	EV.pb({id[v], 1, val});
	EV.pb({id[v] + 1, -1, val});
}

inline int query_min(int L, int R){
	int rk = __lg(R - L + 1);
	//int ret = min(st[L][rk], st[R - (1<<rk) + 1][rk]);
	//cerr<<"query_min("<<L<<", "<<R<<") = "<<ret<<endl;
	return min(st[L][rk], st[R - (1<<rk) + 1][rk]);
}

inline int isanc(int u, int v){
	return (from[u] <= from[v] and to[v] <= to[u]);
}

int query_res(int u, int v){
	int ret = LNF;
	while(fr[u] != fr[v]){
		ret = min(ret, query_min(id[fr[v]], id[v]));
		v = par[fr[v]];
	}
	ret = min(ret, query_min(id[u], id[v]));
	return ret;
}

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	// in
	cin>>n>>shops>>q>>root;
	FOR(i, 1, n-1, 1){
		cin>>eu[i]>>ev[i]>>ew[i];
		edge[eu[i]].eb(ev[i], ew[i]);
		edge[ev[i]].eb(eu[i], ew[i]);
	}
	
	FOR(i, 1, shops, 1){
		int C;
		cin>>C;
		isshop[C] = 1;
	}
	
	// HLD
	find_sz(root, root);
	HLD(root, root, root);
	
	/*
	cerr<<"HLD : ";
	FOR(i, 1, n, 1){
		cerr<<id[i]<<" ";
	}
	cerr<<endl;
	*/
	// HLD ok
	
	// sweep line : 
	
	// events
	FOR(i, 1, n, 1){
		if(isshop[i]) add_seg(i);
		EV.pb({i, 2});
	}
	
	sort(EV.begin(), EV.end());
	
	// min(dep[shop])
	multiset<int> owo;
	for(vi E : EV){
		int type = E[1];
		if(type < 2){ // modify
			int val = E[2];
			if(type == 1){ // insert
				owo.insert(val);
			}
			else if(type == -1){ // erase
				owo.erase(owo.find(val));
			}
		}
		else if(type == 2){ // query
			int Time = E[0];
			if(!owo.empty()) dp[Time] = *owo.begin();
			else dp[Time] = LNF;
		}
	}
	
	// min(dep[shop]) - 2*dep[lca]
	FOR(i, 1, n, 1){
		dp[id[i]] -= 2 * dep[i];
	}
	
	/*
	cerr<<"dp : ";
	FOR(i, 1, n, 1){
		if(dp[i] < LNF / 2) cerr<<dp[i]<<" ";
		else cerr<<"- ";
	}
	cerr<<endl;
	*/	
	// dp ok
	
	// sparse table
	FOR(i, 1, n, 1){
		st[i][0] = dp[i];
	}
	FOR(j, 1, 19, 1){
		FOR(i, 1, n, 1){
			int ii = i + (1<<(j-1));
			if(ii <= n) st[i][j] = min(st[i][j-1], st[ii][j-1]);
			else st[i][j] = st[i][j-1];
		}
	}
	
	// query
	while(q--){
		int ie, qv;
		cin>>ie>>qv;
		
		int iu = eu[ie], iv = ev[ie];
				
		if(isanc(iu, qv) and isanc(iv, qv)){
			// go to shop
			
			if(dep[iu] < dep[iv]) swap(iu, iv);
			
			// can only move in subtree iu
			// query : node iu ~ node qv
			
			// res = min(dep[shop] - 2*dep[lca]) + dep[qv]
			int res = query_res(iu, qv) + dep[qv];
			if(res > LNF / 2) cout<<"oo"<<'\n';
			else cout<<res<<'\n';
		}
		else{
			// escaped
			cout<<"escaped"<<'\n';
		}
	}
	
	return 0;

}

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