oj.uz

Submission #871482

# Submission time Handle Problem Language Result Execution time Memory
871482 2023-11-11T02:41:10 Z 1075508020060209tc File Paths (BOI15_fil) C++14
0 / 100
 10 ms 15704 KB 
//#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 15196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 15704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 15196 KB Output isn't correct
2 Halted 0 ms 0 KB -