oj.uz

답안 #156334

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
156334 2019-10-05T07:24:16 Z amoo_safar File Paths (BOI15_fil) C++14
66 / 100
 1000 ms 38276 KB 
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1e9 + 7;
const int Maxn = 3e3 + 10;
const ll Inf = 1000000000000000LL;

vector<pll> G[Maxn];
vector<pll> Q[Maxn];
vector<ll> R[Maxn];
bool ans[Maxn];
ll dep[Maxn];

map<ll, ll> mp;

void DFS(ll u, ll d = 0){
	dep[u] = d;
	R[u].pb(0);
	mp[d] = 1;
	for(auto E : G[u]){
		ll adj = E.F;
		DFS(adj, d + E.S);
		for(auto x : R[adj]) R[u].pb(x + E.S);
	}
	sort(all(R[u]));
	R[u].resize(unique(all(R[u])) - R[u].begin());
	R[u].shrink_to_fit();
}
ll SS;
ll cnt[1000010];
bool check(ll x){
	if(x < 0) return false;
	if(x == 0) return true;
	assert(x != 0);
	
	return (cnt[x] > 0);
}
ll n;
ll in[Maxn];
map<ll, ll> mp2;

void DFS2(ll u){
	for(auto x: R[u]) cnt[x] ++;
	in[u] = 1;
	for(auto E : G[u]){
		DFS2(E.F);
	}
	
		
	for(auto X : Q[u]){
		ll x = X.F - dep[u];
		mp2.clear();
		for(int i = 0; i <= n; i++){
			if(in[i] == 1) mp2[dep[u] - dep[i]] = 1;
		}
		for(int i = 0; i <= n; i++){
			if(mp2.count(X.F - dep[i] - SS - 1)) ans[X.S] = true;
		}
		//cerr << u << ' ' << X.F << ' ' << x << '\n';
		//if(x >= s + 1) ans[X.S] = (cnt[x - (s + 1)] > 0);
		for(int i = 1; i <= 1000; i++){
			if(x % i == 0){
				ans[X.S] |= check(i - (SS + 1));
				ans[X.S] |= check((x / i) - (SS + 1));
			}
		}
		if(x == 0) ans[X.S] = true;
	}
	in[u] = 0;
	for(auto x : R[u]) cnt[x] --;
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll m, k;
	cin >> n >> m >> k >> SS;
	//assert(k > 10);
	ll p, l;
	for(int i = 1; i <= n; i++){
		cin >> p >> l;
		G[p].pb({i, l + 1});
	}
	for(int i = 1; i <= m; i++){
		cin >> p >> l;
		//assert(l < k-1);
		//assert(p != 0);
		//if(p == 0){
	//		ans[i] = (( (k - l - 1) % (s + 1) ) == 0);
	//	}
		Q[p].pb({k - l - 1, i});
	}
	//cerr << '\n';
	DFS(0);
	DFS2(0);
	
	for(int i = 1; i <= m; i++) cout << (ans[i] ? "YES\n" : "NO\n");
	
	return 0;
}

/*
2 4 22
2
0 1
1 5
2 13
2 10
1 4
0 7

*/

Subtask #1
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 636 KB Output is correct
2 Correct 8 ms 764 KB Output is correct
3 Correct 13 ms 1528 KB Output is correct
4 Correct 23 ms 1912 KB Output is correct
5 Correct 20 ms 8056 KB Output is correct
6 Correct 15 ms 4472 KB Output is correct
7 Correct 36 ms 9592 KB Output is correct
8 Correct 16 ms 5624 KB Output is correct
9 Correct 16 ms 5724 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 12 ms 764 KB Output is correct
12 Correct 20 ms 1912 KB Output is correct

Subtask #2
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 8244 KB Output is correct
2 Correct 137 ms 8156 KB Output is correct
3 Correct 132 ms 8108 KB Output is correct
4 Correct 136 ms 8312 KB Output is correct
5 Correct 783 ms 37456 KB Output is correct
6 Correct 768 ms 37468 KB Output is correct
7 Correct 451 ms 23544 KB Output is correct
8 Correct 449 ms 23560 KB Output is correct
9 Correct 151 ms 9072 KB Output is correct
10 Correct 120 ms 8612 KB Output is correct
11 Correct 173 ms 1976 KB Output is correct
12 Correct 799 ms 32220 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 636 KB Output is correct
2 Correct 8 ms 764 KB Output is correct
3 Correct 13 ms 1528 KB Output is correct
4 Correct 23 ms 1912 KB Output is correct
5 Correct 20 ms 8056 KB Output is correct
6 Correct 15 ms 4472 KB Output is correct
7 Correct 36 ms 9592 KB Output is correct
8 Correct 16 ms 5624 KB Output is correct
9 Correct 16 ms 5724 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 12 ms 764 KB Output is correct
12 Correct 20 ms 1912 KB Output is correct
13 Correct 138 ms 8244 KB Output is correct
14 Correct 137 ms 8156 KB Output is correct
15 Correct 132 ms 8108 KB Output is correct
16 Correct 136 ms 8312 KB Output is correct
17 Correct 783 ms 37456 KB Output is correct
18 Correct 768 ms 37468 KB Output is correct
19 Correct 451 ms 23544 KB Output is correct
20 Correct 449 ms 23560 KB Output is correct
21 Correct 151 ms 9072 KB Output is correct
22 Correct 120 ms 8612 KB Output is correct
23 Correct 173 ms 1976 KB Output is correct
24 Correct 799 ms 32220 KB Output is correct
25 Correct 140 ms 8440 KB Output is correct
26 Correct 139 ms 8176 KB Output is correct
27 Correct 138 ms 8084 KB Output is correct
28 Correct 135 ms 8284 KB Output is correct
29 Correct 786 ms 37304 KB Output is correct
30 Correct 796 ms 37380 KB Output is correct
31 Correct 436 ms 23544 KB Output is correct
32 Correct 436 ms 23416 KB Output is correct
33 Correct 140 ms 8948 KB Output is correct
34 Correct 119 ms 8696 KB Output is correct
35 Correct 175 ms 1892 KB Output is correct
36 Execution timed out 1039 ms 38276 KB Time limit exceeded