oj.uz

Submission #967863

# Submission time Handle Problem Language Result Execution time Memory
967863 2024-04-23T03:13:34 Z ByeWorld Valley (BOI19_valley) C++14
23 / 100
 324 ms 53332 KB 
#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(e, 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 29276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 29276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 45908 KB Output is correct
2 Correct 324 ms 50000 KB Output is correct
3 Correct 307 ms 50004 KB Output is correct
4 Correct 305 ms 51648 KB Output is correct
5 Correct 318 ms 51668 KB Output is correct
6 Correct 323 ms 53332 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 29276 KB Output isn't correct
2 Halted 0 ms 0 KB -