제출 #967861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
967861		ByeWorld	Valley (BOI19_valley)	C++14	0 / 100	309 ms	49744 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 = 4e5+10;
const int INF = 4e18+10;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
const int MX = 1e9+10;

int n, s, q, e;
int u[MAXN], v[MAXN], w[MAXN], type[MAXN];
vector <ipii> adj[MAXN];

int par[MAXN], dep[MAXN], in[MAXN], out[MAXN], tim;
int arr[MAXN], chi[MAXN];
void dfs(int nw, int pa){
	par[nw] = pa; in[nw] = ++tim; arr[tim] = nw;
	dep[nw] = dep[pa]+1;
	for(auto ed : adj[nw]){
		int nx = ed.fi.fi, idx = ed.se;
		if(nx==pa) continue;
		chi[idx] = nx;
		dfs(nx, nw);
	}
	out[nw] = ++tim; arr[tim] = -nw;
}

struct fen {
	int st[2*MAXN];
	void upd(int x, int p){
		for(; x<=2*MAXN-20; x+=(x&(-x))) st[x] += p;
	}
	int que(int x){
		int te = 0;
		for(; x>=1; x-=(x&(-x))) te += st[x];
		return te;
	}
} A;

signed main(){
	// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	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]}, i});
		adj[v[i]].pb({{u[i], w[i]}, i});
	}
	dfs(1, 0);
	for(int i=1; i<=s; i++){
		int x; cin >> x;
		type[x] = 1;
	}
	for(int XX=1; XX<=q; XX++){
		int idx, sta; cin >> idx >> sta;
		int node = chi[idx]; // upd child dari edge
		A.upd(in[node], 1); A.upd(out[node], -1);

		if(A.que(in[sta]) == 0){ // masi bisa ke root
			cout << "escaped\n";
		} else {
			cout << "0\n";
		}
		A.upd(in[node], -1); A.upd(out[node], 1);
	}
}

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