Submission #953109

#TimeUsernameProblemLanguageResultExecution timeMemory
953109PM1File Paths (BOI15_fil)C++17
0 / 100
1054 ms2652 KiB
#include <bits/stdc++.h> using namespace std; const int mxn=3e3+5,mxs=1e6+5; int n,m,s,k,par[mxn*2],dis[mxn*2]; bitset<mxn>b[mxs]; vector<int>all,v[mxn]; bool mark[mxs],ans[mxn*2]; void make(int x,bool y){ int z=x; while(x!=0){ x=par[x]; int d=dis[z]-dis[x]; if(d<=k)mark[d]=y; } } void dfs(int z){ b[z]=((b[par[z]]<<(dis[z]-dis[par[z]]))|b[par[z]]); b[z][s]=1; for(auto i:v[z]){ dfs(i); } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m>>k>>s; s++; for(int i=1;i<=n+m;i++){ int x,y; cin>>x>>y; par[i]=x; dis[i]=dis[x]+y+1; if(i<=n){ all.push_back(dis[i]); v[x].push_back(i); } } all.push_back(0); for(int i=n+1;i<=n+m;i++){ make(i,1); if(dis[i]==k)ans[i]=1; for(auto j:all){ int res=k-j-s; if(res>=0 && mark[res])ans[i]=1; } make(i,0); } dfs(0); for(int i=n+1;i<=n+m;i++){ int x=k-dis[i]; for(int j=1;j<=x;j++){ if(x%j==0 && b[par[i]][x/j]==1)ans[i]=1; } } for(int i=n+1;i<=n+m;i++){ if(ans[i]) cout<<"YES"<<'\n'; else cout<<"NO"<<'\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...