oj.uz

Submission #493035

# Submission time Handle Problem Language Result Execution time Memory
493035 2021-12-10T03:41:44 Z Haruto810198 Valley (BOI19_valley) C++17
100 / 100
 937 ms 116836 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2892 KB Output is correct
2 Correct 4 ms 2892 KB Output is correct
3 Correct 4 ms 2892 KB Output is correct
4 Correct 4 ms 2892 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2892 KB Output is correct
2 Correct 4 ms 2892 KB Output is correct
3 Correct 4 ms 2892 KB Output is correct
4 Correct 4 ms 2892 KB Output is correct
5 Correct 4 ms 3148 KB Output is correct
6 Correct 3 ms 3148 KB Output is correct
7 Correct 2 ms 3148 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Correct 4 ms 3148 KB Output is correct
10 Correct 3 ms 3148 KB Output is correct
11 Correct 7 ms 3624 KB Output is correct
12 Correct 5 ms 3592 KB Output is correct
13 Correct 4 ms 3532 KB Output is correct
14 Correct 2 ms 3212 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 817 ms 108288 KB Output is correct
2 Correct 937 ms 116836 KB Output is correct
3 Correct 900 ms 112224 KB Output is correct
4 Correct 627 ms 91064 KB Output is correct
5 Correct 641 ms 92568 KB Output is correct
6 Correct 475 ms 77564 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2892 KB Output is correct
2 Correct 4 ms 2892 KB Output is correct
3 Correct 4 ms 2892 KB Output is correct
4 Correct 4 ms 2892 KB Output is correct
5 Correct 4 ms 3148 KB Output is correct
6 Correct 3 ms 3148 KB Output is correct
7 Correct 2 ms 3148 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Correct 4 ms 3148 KB Output is correct
10 Correct 3 ms 3148 KB Output is correct
11 Correct 7 ms 3624 KB Output is correct
12 Correct 5 ms 3592 KB Output is correct
13 Correct 4 ms 3532 KB Output is correct
14 Correct 2 ms 3212 KB Output is correct
15 Correct 817 ms 108288 KB Output is correct
16 Correct 937 ms 116836 KB Output is correct
17 Correct 900 ms 112224 KB Output is correct
18 Correct 627 ms 91064 KB Output is correct
19 Correct 641 ms 92568 KB Output is correct
20 Correct 475 ms 77564 KB Output is correct
21 Correct 137 ms 42264 KB Output is correct
22 Correct 155 ms 42132 KB Output is correct
23 Correct 153 ms 42132 KB Output is correct
24 Correct 156 ms 44124 KB Output is correct
25 Correct 162 ms 47036 KB Output is correct
26 Correct 140 ms 42396 KB Output is correct
27 Correct 138 ms 42220 KB Output is correct
28 Correct 147 ms 42288 KB Output is correct
29 Correct 159 ms 43688 KB Output is correct
30 Correct 156 ms 45132 KB Output is correct
31 Correct 171 ms 48848 KB Output is correct
32 Correct 219 ms 49952 KB Output is correct
33 Correct 219 ms 49316 KB Output is correct
34 Correct 192 ms 48424 KB Output is correct
35 Correct 193 ms 50468 KB Output is correct
36 Correct 228 ms 54848 KB Output is correct