oj.uz

Submission #1021020

# Submission time Handle Problem Language Result Execution time Memory
1021020 2024-07-12T12:57:32 Z owoovo File Paths (BOI15_fil) C++17
0 / 100
 522 ms 262144 KB 
#include<bits/stdc++.h>
#define ll long long
#define F first 
#define S second 
using namespace std;
int n,m,s,k,f[3010],l[3010],dep[3010];
set<int> sub[3010],ring[3010],path[3010];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>k>>s;
    s++;
    for(int i=1;i<=n;i++){
        cin>>f[i]>>l[i];
        l[i]++;
    }
    for(int i=1;i<=n;i++){
        dep[i]=dep[f[i]]+l[i];
    }
    for(int i=n;i>=0;i--){
        sub[i].insert(dep[i]);
        for(auto x:sub[i]){
            sub[f[i]].insert(x);
        }
    }
    for(int i=0;i<=n;i++){
        for(auto x:sub[i]){
            ring[i].insert(x-dep[i]);
        }
        for(auto x:ring[f[i]]){
            ring[i].insert(x);
        }
    }
    for(int i=0;i<=n;i++)sub[i].clear();
    for(int i=0;i<=n;i++){
        sub[i].insert(dep[i]);
        for(auto x:sub[f[i]]){
            sub[i].insert(x);
        }
    }
    for(int i=0;i<=n;i++){
        for(auto x:sub[i]){
            path[i].insert(dep[i]-x);
        }
        for(auto x:path[f[i]]){
            path[i].insert(x);
        }
    }
    for(int i=0;i<m;i++){
        int a,b,tar=k,ok=0;
        cin>>a>>b;
        tar-=dep[a];
        tar-=b+1;
        if(tar==0){
            ok=1;
        }
        if(path[a].find(-tar+s)!=path[a].end())ok=1;
        if(ring[a].find(tar-s)!=ring[a].end())ok=1;
        if(ok){
            cout<<"YES\n";
        }else{
            cout<<"NO\n";
        }
    }
    return 0;
}

Subtask #1
0 / 33.0

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

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 522 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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