Submission #943842

#	Time	Username	Problem	Language	Result	Execution time	Memory
943842		pcc	Valley (BOI19_valley)	C++17	23 / 100	73 ms	27732 KiB

valley

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 2e5+10;
vector<pii> t1[mxn],t2[mxn];
int ptr = 0;
int N,S,Q,E;
pair<pii,int> req[mxn];
bitset<mxn> esc;
ll ans[mxn];
pii eid[mxn];
bitset<mxn> shop;

namespace ESC{
	int pt = 0;
	pii eul[mxn];
	void dfs(int now,int par){
		eul[now].fs = ++pt;
		for(auto nxt:t1[now]){
			if(nxt.fs == par)continue;
			dfs(nxt.fs,now);
		}
		eul[now].sc = pt;
	}
	bool peko(pii r,int p){
		return r.fs<=p&&p<=r.sc;
	}
	void GO(){
		dfs(E,E);
		esc.set();
		for(int i = 1;i<=Q;i++){
			auto [a,b] = req[i].fs;
			auto c = req[i].sc;
			if(peko(eul[a],eul[c].fs)&&peko(eul[b],eul[c].fs))esc[i] = false;
		}
		return;
	}
}

namespace CD{
	void GO(){
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>S>>Q>>E;
	for(int i = 1;i<N;i++){
		int a,b,c;
		cin>>a>>b>>c;
		t1[a].push_back({b,c});
		t1[b].push_back({a,c});
		eid[i] = {a,b};
	}
	for(int i = 1;i<=S;i++){
		int k;
		cin>>k;
		shop[k] = true;
	}
	for(int i = 1;i<=Q;i++){
		int id,p;
		cin>>id>>p;
		req[i] = {eid[id],p};
	}
	ESC::GO();
	for(int i = 1;i<=Q;i++){
		cout<<(esc[i]?"escaped\n":"0\n");
	}
	CD::GO();
	return 0;
}

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