Submission #206092

#	Time	Username	Problem	Language	Result	Execution time	Memory
206092		alishahali1382	Valley (BOI19_valley)	C++14	100 / 100	366 ms	24312 KiB

valley

#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 100010, LOG=20;

int n, m, q, k, u, v, x, y, t, a, b, root;
int E[MAXN][3];
int stt[MAXN], fnt[MAXN], timer=1;
int par[MAXN], parid[MAXN];
ll seg[MAXN<<2], lazy[MAXN<<2];
ll ans[MAXN];
vector<int> G[MAXN];
vector<pii> Q[MAXN];

void add_lazy(int id, ll val){
	seg[id]+=val;
	lazy[id]+=val;
}

void shift(int id){
	if (!lazy[id]) return ;
	add_lazy(id<<1, lazy[id]);
	add_lazy(id<<1 | 1, lazy[id]);
	lazy[id]=0;
}

void Add(int id, int tl, int tr, int l, int r, ll val){
	if (r<=tl || tr<=l) return ;
	if (l<=tl && tr<=r){
		add_lazy(id, val);
		return ;
	}
	shift(id);
	int mid=(tl+tr)>>1;
	Add(id<<1, tl, mid, l, r, val);
	Add(id<<1 | 1, mid, tr, l, r, val);
	seg[id]=min(seg[id<<1], seg[id<<1 | 1]);
}

ll Get(int id, int tl, int tr, int l, int r){
	if (r<=tl || tr<=l) return seg[0];
	if (l<=tl && tr<=r) return seg[id];
	shift(id);
	int mid=(tl+tr)>>1;
	return min(Get(id<<1, tl, mid, l, r), Get(id<<1 | 1, mid, tr, l, r));
}

void dfs1(int node){
	stt[node]=timer++;
	for (int v:G[node]) if (v!=par[node]){
		par[v]=node;
		dfs1(v);
	}
	fnt[node]=timer;
}

void dfs2(int node){
	for (pii p:Q[node]) ans[p.second]=Get(1, 1, n+1, stt[p.first], fnt[p.first]);
	for (int v:G[node]) if (v!=par[node]){
		int id=parid[v];
		Add(1, 1, n+1, 1, n+1, E[id][2]);
		Add(1, 1, n+1, stt[v], fnt[v], -2*E[id][2]);
		dfs2(v);
		Add(1, 1, n+1, 1, n+1, -E[id][2]);
		Add(1, 1, n+1, stt[v], fnt[v], 2*E[id][2]);
	}
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	seg[0]=INF;
	cin>>n>>m>>q>>root;
	for (int i=1; i<n; i++){
		cin>>E[i][0]>>E[i][1]>>E[i][2];
		G[E[i][0]].pb(E[i][1]);
		G[E[i][1]].pb(E[i][0]);
	}
	dfs1(root);
	while (m--){
		cin>>v;
		Add(1, 1, n+1, stt[v], stt[v]+1, -INF);
	}
	Add(1, 1, n+1, 1, n+1, +INF);
	for (int i=1; i<n; i++){
		if (par[E[i][0]]!=E[i][1]) swap(E[i][0], E[i][1]);
		parid[E[i][0]]=i;
		Add(1, 1, n+1, stt[E[i][0]], fnt[E[i][0]], E[i][2]);
	}
	
	for (int i=1; i<=q; i++){
		cin>>x>>v;
		if (stt[E[x][0]]<=stt[v] && fnt[v]<=fnt[E[x][0]]) Q[v].pb({E[x][0], i});
		else ans[i]=-1;
	}
	dfs2(root);
	
	for (int i=1; i<=q; i++){
		if (ans[i]<0) cout<<"escaped\n";
		else if (ans[i]>=INF) cout<<"oo\n";
		else cout<<ans[i]<<'\n';
	}
	
	return 0;
}

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