제출 #1256080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256080		nlsosad	Valley (BOI19_valley)	C++20	100 / 100	364 ms	43288 KiB

valley

#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
int inf = 1e18;
int depth[100001], dist[100001], res[100001];
pair<int, int> edge[100001];
vector<bool> store(100001, false);
vector<pair<int, int>> a[100001], query[200001];
vector<int> pos[100001];
vector<int> e, luu;
vector<bool> vst(100001, false);
struct segtree{
	int n;
	vector<int> tr, lazy;
	vector<int> mtr;
	segtree(int m){
		int n = m;
		tr.resize(4*m, 0); //Real
		lazy.resize(4*m, inf);
		mtr.resize(4*m, 0); //Min segtree
	}
	void build(int node, int l, int r){
		if(l==r){
			mtr[node] = dist[e[luu[l]]];
			tr[node] = -dist[e[luu[l]]];
		}else{
			int mid = (l+r)/2;
			build(2*node, l, mid);
			build(2*node+1, mid+1, r);
			mtr[node] = min(mtr[2*node], mtr[2*node+1]);
			tr[node] = min(tr[2*node], tr[2*node+1]);
		}
	}
	void propa(int node, int l, int r){
		if(lazy[node]!=inf){
			int mn = mtr[node];
			int d = dist[lazy[node]];
			tr[node] = mn - 2*d;
			// cout << node << ' ' << l << ' ' << r << ' ' << tr[node] << ' ' << lazy[node] << '\n';
			if(l!=r){
				if(lazy[2*node]==inf or depth[lazy[2*node]] > depth[lazy[node]]){
					lazy[2*node] = lazy[node];
				}
				if(lazy[2*node+1]==inf or depth[lazy[2*node+1]] > depth[lazy[node]]){
					lazy[2*node+1] = lazy[node];
				}
			}
		}
	}
	void update(int node, int start, int end, int l, int r, int u){
		propa(node, start, end);
		if(start > r or end < l){
			return;
		}
		if(l<=start and end<=r){
			if(lazy[node]==inf or depth[lazy[node]] > depth[u]){
				lazy[node] = u;
			}
			propa(node, start, end);
			return;
		}
		int mid = (start+end)/2;
		update(2*node, start, mid, l, r, u);
		update(2*node+1, mid+1, end, l, r, u);
		tr[node] = min(tr[2*node], tr[2*node+1]);
	}
	int query(int node, int start, int end, int l, int r){
		propa(node, start, end);
		if(start>r or end < l){
			return inf;
		}
		if(l<=start and end<=r){
			return tr[node];
		}
		int mid = (start+end)/2;
		return min(query(2*node, start, mid, l, r), query(2*node+1, mid+1, end, l, r));
	}
};
void dfs(int u){
	vst[u] = true;
	e.push_back(u);
	for (auto [v, w]:a[u]){
		if(!vst[v]){
			depth[v] = depth[u] +1;
			dist[v]=dist[u]+w;
			dfs(v);
			e.push_back(u);
		}
	}
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	e.push_back(-1);
	luu.push_back(-1);
	int n, s, q, E;
	cin >> n >> s >> q >> E;
	for (int i = 1;i<n;++i){
		int u, v, w;
		cin >> u >> v >> w;
		edge[i] = {u, v};
		a[u].push_back({v, w});
		a[v].push_back({u, w});
	}
	dfs(1);
	for (int i =1;i<=s;++i){
		int u;
		cin >> u;
		store[u] = true;
	}
	int m = e.size()-1;
	for (int i = 1;i<=m;++i){
		pos[e[i]].push_back(i);
	}
	for (int i = 1;i<=m;++i){
		if(store[e[i]] and pos[e[i]][0]==i){
			luu.push_back(i);
		}
	}
	int len = luu.size()-1;
	for (int i = 1;i<=m;++i){
		// cout << e[i] << ' ';
	}
	// cout << '\n';
	for (int i= 1;i<=len;++i){
		// cout << e[luu[i]] << ' ';
	}
	segtree cay(len);
	cay.build(1, 1, len);
	for (int j = 1;j<=q;++j){
		res[j] = inf;
		int i, rr;
		cin >> i >> rr;
		auto [u, v] = edge[i];
		if(depth[u] > depth[v])swap(u, v);
		int x = pos[rr][0], y = pos[E][0];
		int l = pos[v][0], r = pos[v].back();
		if((l<=x and x<=r and (y<l or y>r)) or (l<=y and y<=r and(x<l or x>r))){
			query[x].push_back({i, j});
		}else{
			res[j] = -1;
		}
	}
	stack<int> st;
	for (int i = 1;i<=m;++i){
		while(!st.empty() and depth[e[st.top()]]>=depth[e[i]]){
			st.pop();
		}
		int dau = 0;
		if(st.empty())dau = 1;
		else{
			dau = upper_bound(luu.begin(), luu.end(), st.top())-luu.begin();
		}
		int cuoi = upper_bound(luu.begin(), luu.end(), i)-luu.begin()-1;
		cay.update(1, 1,len, dau, cuoi, e[i]);
		// cout << dau << ' ' << cuoi << '\n';
		st.push(i);
		for (auto [j, id]:query[i]){
			// cout << j << ' ' << id << '\n';
			int rr = e[i];
			auto [u, v] = edge[j];
			if(depth[u] > depth[v])swap(u, v);
			int x = pos[rr][0];
			int l = pos[v][0], r = pos[v].back();
			if(x<l){
				dau = 1;
				cuoi = upper_bound(luu.begin(), luu.end(), i)-luu.begin()-1;
				int sol = cay.query(1, 1, len, dau, cuoi);
				// cout << sol << " NGU 1\n";
				if(sol!=inf)res[id] = min(res[id], dist[rr]+sol);
			}else if(x>r){
				dau = upper_bound(luu.begin(), luu.end(), r)-luu.begin();
				cuoi = upper_bound(luu.begin(), luu.end(), i)-luu.begin()-1;
				int sol = cay.query(1, 1, len, dau, cuoi);
				// cout << sol << " NGU 2\n";
				if(sol!=inf)res[id] = min(res[id], dist[rr]+sol);
				dau = 1;
				cuoi = lower_bound(luu.begin(), luu.end(), l)-luu.begin()-1;
				sol = cay.query(1, 1, len, dau, cuoi);
				// cout << sol << " NGU 3\n";
				if(sol!=inf)res[id] = min(res[id], dist[rr]+sol);
			}else{
				dau = lower_bound(luu.begin(), luu.end(), l)-luu.begin();
				cuoi = upper_bound(luu.begin(), luu.end(), i)-luu.begin()-1;
				// cout << dau << ' ' << cuoi << " LON\n";
				int sol = cay.query(1, 1, len, dau, cuoi);
				// cout << sol << " NGU 4\n";
				if(sol!=inf)res[id] = min(res[id], dist[rr]+sol);
			}
		}
	}
	cay.build(1, 1, len);
	for (int i = 0;i<4*len;++i){
		cay.lazy[i] = inf;
	}
	while(!st.empty()){
		st.pop();
	}
	// return 0;
	for (int i = m;i>=1;--i){
		while(!st.empty() and depth[e[st.top()]]>=depth[e[i]]){
			st.pop();
		}
		int dau = 0;
		int cuoi = 0;
		dau = lower_bound(luu.begin(), luu.end(), i)-luu.begin();
		if(st.empty())cuoi = len;
		else{
			cuoi = upper_bound(luu.begin(), luu.end(), st.top())-luu.begin()-1;
		}
		cay.update(1, 1,len, dau, cuoi, e[i]);
		st.push(i);
		for (auto [j, id]:query[i]){
			// cout << j << ' ' << id << '\n';
			int rr = e[i];
			auto [u, v] = edge[j];
			if(depth[u] > depth[v])swap(u, v);
			int x = pos[rr][0];
			int l = pos[v][0], r = pos[v].back();
			if(x<l){
				dau = lower_bound(luu.begin(), luu.end(), i)-luu.begin();
				cuoi = lower_bound(luu.begin(), luu.end(), l)-luu.begin()-1;
				int sol = cay.query(1, 1, len, dau, cuoi);
				// cout << sol << " NGU 1\n";
				if(sol!=inf)res[id] = min(res[id], dist[rr]+sol);
				dau = upper_bound(luu.begin(), luu.end(), r)-luu.begin();
				cuoi = len;
				sol = cay.query(1, 1, len, dau, cuoi);
				// cout << sol << " NGU 2\n";
				if(sol!=inf)res[id] = min(res[id], dist[rr]+sol);
			}else if(x>r){
				dau = lower_bound(luu.begin(), luu.end(), i)-luu.begin();
				cuoi = len;
				int sol = cay.query(1, 1, len, dau, cuoi);
				// cout << sol << " NGU 3\n";
				if(sol!=inf)res[id] = min(res[id], dist[rr]+sol);
			}else{
				dau = lower_bound(luu.begin(), luu.end(), i)-luu.begin();
				cuoi = upper_bound(luu.begin(), luu.end(), r)-luu.begin()-1;
				// cout << dau << ' ' << cuoi << " LON\n";
				int sol = cay.query(1, 1, len, dau, cuoi);
				// cout << sol << " NGU 4\n";
				if(sol!=inf)res[id] = min(res[id], dist[rr]+sol);
			}
		}
	}
	for (int i = 1;i<=q;++i){
		if(res[i]==inf){
			cout << "oo\n";
		}else if(res[i]==-1){
			cout << "escaped\n";
		}else cout << res[i] << '\n';
	}
}

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