Submission #668666

#TimeUsernameProblemLanguageResultExecution timeMemory
668666KahouFile Paths (BOI15_fil)C++14
33 / 100
1096 ms55884 KiB
#include<bits/stdc++.h> using namespace std; #define F first #define S second #define endl '\n' #define mk make_pair typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int N = 6050; int n, m, h[N], k, s, p[N]; vector<int> vc[N]; vector<int> vt[N]; void solve() { cin >> n >> m >> k; cin >> s; s++; vc[0].push_back(0); p[0] = -1; for (int u = 1; u <= n+m; u++) { int l; cin >> p[u] >> l; l++; h[u] = h[p[u]]+l; vc[u] = vc[p[u]]; if (u <= n) vc[u].push_back(h[u]); } for (int u = 0; u <= n; u++) { int v = u; while (v >= 0) { vt[v].push_back(h[u]-h[v]+s); v = p[v]; } } sort(h, h+n+1); for (int u = n+1; u <= n+m; u++) { bool flg = (h[u] == k); for (int x:vc[u]) { int v = lower_bound(h, h+n+1, k-s-(h[u]-x))-h; if (h[v] + s + h[u]-x == k) flg = 1; } int T = k- h[u]; int v = u; while (v >= 0) { for (int d:vt[v]) { if (T%d == 0) flg = 1; } v = p[v]; } cout << (flg? "YES":"NO") << endl; } } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...