Submission #980623

#	Time	Username	Problem	Language	Result	Execution time	Memory
980623		ByeWorld	Valley (BOI19_valley)	C++14	100 / 100	249 ms	58060 KiB

valley

#include <bits/stdc++.h>
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
const int MAXN = 2e5+10;
const int INF = 1e18+10;
const int LOG = 18; 
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;

struct seg {
	int st[4*MAXN];
	void bd(int id, int l, int r){
		st[id] = INF;
		if(l==r) return;
		bd(lf, l, md); bd(rg, md+1, r);
	}
	int que(int id, int l, int r, int x, int y){
		if(x<=l && r<=y) return st[id];
		if(r<x || y<l) return INF;
		return min(que(lf, l, md, x, y), que(rg, md+1, r, x, y));
	}
	int upd(int id, int l, int r, int x, int p){
		if(l==r && x==l) return st[id] = p;
		if(x<l || r<x) return st[id];
		return st[id] = min(upd(lf, l, md, x, p), upd(rg, md+1, r, x, p));
	}
} A;
int n, s, q, e;
int u[MAXN], v[MAXN], w[MAXN], ty[MAXN];
vector <pii> adj[MAXN], que[MAXN];
int dis[MAXN], dep[MAXN], dw[MAXN], ans[MAXN], up[MAXN];

void pre(int nw, int par){
	// cout << nw << ' ' << par << " nw\n";
	dep[nw] = dep[par]+1; 
	dis[nw] = INF;
	for(auto ed : adj[nw]){
		int nx = ed.fi, wei = ed.se;
		if(nx == par) continue;
		up[nx] = up[nw]+wei;
		pre(nx, nw);
		dis[nw] = min(dis[nw], dis[nx]+wei);
	}
	if(ty[nw]) dis[nw] = 0;
}
vector <int> vec;
void dfs(int nw, int par){
	A.upd(1, 1, n, dep[nw], dis[nw]-up[nw]);
	vec.pb(nw);
	for(auto ed : adj[nw]){
		int nx = ed.fi, wei = ed.se;
		if(nx == par) continue;
		dfs(nx, nw);
	}
	for(auto in : que[nw]){
		int ed = in.fi, idx = in.se;
		// cout << idx <<  ' ' << dw[ed] << ' '<< dep[dw[ed]] << " idx\n";
		// for(auto in : vec) cout << in << ' ';
		// 	cout << '\n';
		if(vec.size()-1 < dep[dw[ed]] || vec[dep[dw[ed]]] != dw[ed]){
			ans[idx] = -1; continue;
		}
		// ans[idx] = 0;
		ans[idx] = A.que(1, 1, n, dep[dw[ed]], dep[nw])+up[nw];
	}
	vec.pop_back();
	A.upd(1, 1, n, dep[nw], INF);
}
signed main(){
	cin >> n >> s >> q >> e;
	for(int i=1; i<=n-1; i++){
		cin >> u[i] >> v[i] >> w[i];
		adj[u[i]].pb({v[i], w[i]});
		adj[v[i]].pb({u[i], w[i]});
	}
	A.bd(1, 1, n);
	for(int i=1; i<=s; i++){
		int c; cin >> c; ty[c] = 1;
	}
	pre(e, 0);
	for(int i=1; i<=n-1; i++){
		dw[i] = (dep[u[i]] < dep[v[i]] ? v[i] : u[i]);
	}
	// for(int i=1; i<=n; i++){
	// 	cout << i << ' ' << up[i] << " dw\n";
	// }
	for(int i=1; i<=q; i++){
		int ed, idx; cin >> ed >> idx;
		que[idx].pb({ed, i});
	}
	vec.pb(-1);
	dfs(e, 0);
	for(int i=1; i<=q; i++){
		if(ans[i] == -1) cout << "escaped\n";
		else if(ans[i] >= INF) cout << "oo\n";
		else cout << ans[i] << '\n';
	}
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(long long int, long long int)':
valley.cpp:59:19: warning: unused variable 'wei' [-Wunused-variable]
   59 |   int nx = ed.fi, wei = ed.se;
      |                   ^~~
valley.cpp:68:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   68 |   if(vec.size()-1 < dep[dw[ed]] || vec[dep[dw[ed]]] != dw[ed]){
      |      ~~~~~~~~~~~~~^~~~~~~~~~~~~

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