Submission #546978

#TimeUsernameProblemLanguageResultExecution timeMemory
546978OttoTheDinoFile Paths (BOI15_fil)C++17
33 / 100
1086 ms58044 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i,s,e) for (ll i = s; i <= e; ++i) #define rrep(i,s,e) for (ll i = s; i >= e; --i) #define pb push_back #define pf push_front #define fi first #define se second #define all(a) a.begin(), a.end() #define SZ(a) (ll)a.size() typedef long long ll; typedef pair<ll, ll> ii; typedef vector<ii> vii; typedef vector<ll> vi; typedef vector<double> vd; typedef vector<string> vs; typedef vector<ll> vll; const ll mx = 3e3; vi adj[mx+1], files[mx+1]; ll cost[mx+1], costf[mx+1], ans[mx+1], s, k, p[mx+1]; unordered_map<ll,ll> cnt, spec; void dfs3 (ll u, ll cur){ if (cur>1e6) return; spec[cur] = 1; for (ll v : adj[u]) { dfs3 (v, cur + cost[v]); } } void dfs2 (ll u, ll cur, ll d) { if (cur>1e6) return; cnt[cur] += d; for (ll v : adj[u]) dfs2 (v, cur+cost[v], d); } void dfs (ll u, ll cur) { if (cur>1e6) return; dfs2 (u, 0, 1); for (ll v : adj[u]) dfs (v, cur + cost[v]); for (ll v : files[u]) { ll x = k - cur - costf[v]; if (x==0) ans[v] = 1; for (ll i = 1; i*i <= x; ++i) { if (x%i==0) { if (cnt[i-s]) ans[v] = 1; if (cnt[x/i-s]) ans[v] = 1; } } ll go = u, cur2 = 0; while (go>=0) { if (spec[k-costf[v]-cur2-s]) ans[v] = 1; cur2 += cost[go]; go = p[go]; } } dfs2 (u, 0, -1); } int main() { ios::sync_with_stdio(0); cin.tie(0); ll n, m; cin >> n >> m >> k >> s; ++s; p[0] = -1; rep (i,1,n) { cin >> p[i] >> cost[i]; ++cost[i]; adj[p[i]].pb(i); } rep (i,1,m) { ll pr; cin >> pr >> costf[i]; ++costf[i]; files[pr].pb(i); } dfs3(0,0); dfs (0,0); rep (i,1,m) cout << (ans[i]?"YES":"NO") << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...