oj.uz

답안 #943842

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
943842 2024-03-12T02:15:34 Z pcc Valley (BOI19_valley) C++17
23 / 100
 73 ms 27732 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 14684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 14684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 25172 KB Output is correct
2 Correct 66 ms 25168 KB Output is correct
3 Correct 65 ms 24784 KB Output is correct
4 Correct 62 ms 26196 KB Output is correct
5 Correct 58 ms 26496 KB Output is correct
6 Correct 65 ms 27732 KB Output is correct

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 14684 KB Output isn't correct
2 Halted 0 ms 0 KB -