oj.uz

Submission #161652

# Submission time Handle Problem Language Result Execution time Memory
161652 2019-11-03T12:52:25 Z amoo_safar File Paths (BOI15_fil) C++14
66 / 100
 1000 ms 38264 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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 8 ms 632 KB Output is correct
3 Correct 14 ms 1400 KB Output is correct
4 Correct 23 ms 2040 KB Output is correct
5 Correct 20 ms 8056 KB Output is correct
6 Correct 15 ms 4472 KB Output is correct
7 Correct 37 ms 9464 KB Output is correct
8 Correct 17 ms 5624 KB Output is correct
9 Correct 17 ms 5756 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 11 ms 632 KB Output is correct
12 Correct 20 ms 2040 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 8188 KB Output is correct
2 Correct 137 ms 8188 KB Output is correct
3 Correct 132 ms 8044 KB Output is correct
4 Correct 136 ms 8364 KB Output is correct
5 Correct 782 ms 37492 KB Output is correct
6 Correct 762 ms 37496 KB Output is correct
7 Correct 455 ms 23544 KB Output is correct
8 Correct 458 ms 23672 KB Output is correct
9 Correct 155 ms 9080 KB Output is correct
10 Correct 120 ms 8712 KB Output is correct
11 Correct 169 ms 2048 KB Output is correct
12 Correct 790 ms 32128 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 8 ms 632 KB Output is correct
3 Correct 14 ms 1400 KB Output is correct
4 Correct 23 ms 2040 KB Output is correct
5 Correct 20 ms 8056 KB Output is correct
6 Correct 15 ms 4472 KB Output is correct
7 Correct 37 ms 9464 KB Output is correct
8 Correct 17 ms 5624 KB Output is correct
9 Correct 17 ms 5756 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 11 ms 632 KB Output is correct
12 Correct 20 ms 2040 KB Output is correct
13 Correct 139 ms 8188 KB Output is correct
14 Correct 137 ms 8188 KB Output is correct
15 Correct 132 ms 8044 KB Output is correct
16 Correct 136 ms 8364 KB Output is correct
17 Correct 782 ms 37492 KB Output is correct
18 Correct 762 ms 37496 KB Output is correct
19 Correct 455 ms 23544 KB Output is correct
20 Correct 458 ms 23672 KB Output is correct
21 Correct 155 ms 9080 KB Output is correct
22 Correct 120 ms 8712 KB Output is correct
23 Correct 169 ms 2048 KB Output is correct
24 Correct 790 ms 32128 KB Output is correct
25 Correct 141 ms 8304 KB Output is correct
26 Correct 139 ms 8264 KB Output is correct
27 Correct 138 ms 8184 KB Output is correct
28 Correct 136 ms 8176 KB Output is correct
29 Correct 796 ms 37288 KB Output is correct
30 Correct 800 ms 37496 KB Output is correct
31 Correct 483 ms 23544 KB Output is correct
32 Correct 440 ms 23416 KB Output is correct
33 Correct 141 ms 8952 KB Output is correct
34 Correct 119 ms 8696 KB Output is correct
35 Correct 173 ms 1912 KB Output is correct
36 Execution timed out 1030 ms 38264 KB Time limit exceeded