Submission #161653

#	Time	Username	Problem	Language	Result	Execution time	Memory
161653		amoo_safar	File Paths (BOI15_fil)	C++14	100 / 100	934 ms	19848 KiB

fil

    #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 int 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
     
    */

Compilation message (stderr)

fil.cpp:17:20: warning: overflow in implicit constant conversion [-Woverflow]
     const ll Inf = 1000000000000000LL;
                    ^~~~~~~~~~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 33 / 33
• Subtask 3: 34 / 34