제출 #1021020

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1021020		owoovo	File Paths (BOI15_fil)	C++17	0 / 100	522 ms	262144 KiB

fil

#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
• Subtask 2: 0 / 33
• Subtask 3: 0 / 34