Submission #871482

#	Time	Username	Problem	Language	Result	Execution time	Memory
871482		1075508020060209tc	File Paths (BOI15_fil)	C++14	0 / 100	10 ms	15704 KiB

fil

//#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
//#include <bits/extc++.h>
//using namespace __gnu_pbds;
using namespace std;
#define int long long
#define X first
#define Y second
int n;int Q;int S;int K;
vector<pair<int,int>>e[500005];
int dph[500005];
int dis[500005];
int fa[500005];
int wf[500005];
unordered_map<int,int>mp;
void dfs(int nw){
for(int i=0;i<e[nw].size();i++){
    int v=e[nw][i].first;
    dph[v]=dph[nw]+1;
    dis[v]=dis[nw]+e[nw][i].second;
    dfs(v);
}
mp[dis[nw]]++;
}




signed main(){
cin>>n>>Q>>K>>S;
n++;
S++;
for(int i=2;i<=n;i++){
    cin>>fa[i]>>wf[i];
    fa[i]++;
    wf[i]++;
    e[fa[i]].push_back({i,wf[i]});
}
dfs(1);
while(Q--){
    int v;int len;
    cin>>v>>len;

    len++;
    v++;
    int ok=0;
    if(dis[v]+len==K){
        cout<<"YES\n";
        continue;
    }


    int nwd=len;
    int nw=v;
    while(1){
        mp[dis[nw]]--;
        int nd=K-nwd;
        if(mp[nd]){
            mp[dis[nw]]++;
            ok=1;break;
        }
        mp[dis[nw]]++;
        if(nw==1){break;}
        nwd=nwd+wf[nw];
        nw=fa[nw];
    }
    if(ok){
        cout<<"YES\n";continue;
    }cout<<"NO\n";

}



}

Compilation message (stderr)

fil.cpp: In function 'void dfs(long long int)':
fil.cpp:17:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~

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