oj.uz

Submission #668660

# Submission time Handle Problem Language Result Execution time Memory
668660 2022-12-04T11:05:23 Z mhn2 File Paths (BOI15_fil) C++17
33 / 100
 503 ms 171836 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
#define pb push_back
#define endl '\n'
using namespace std;

const int N = 3005, K = 1e6+5, X = 5, Y = K/X+100;
int nn, mm, kk, ss;
bool ad[K], ans[N];
int pr[N], wt[N];
ll c1[K], c2[Y], ds[N], pd[K];
vector<ll> a1[N], a2[N];
vector<int> ch[N];
vector<pii> qr[N];

void dfs1(int v, int s, ll w) {
    w += wt[v];
    if (w < Y) {
        a2[s].pb(w);
        c2[w]++;
    }
    for (int i = 2; i <= X; i++)
        if (w * i < K) {
            a1[s].pb(w * i);
            c1[w*i]++;
        }

    for (int u : ch[v])
        dfs1(u, s, w);
}

void dfs2(int v) {
    dfs1(v, v, ss-wt[v]);

    /*for (int i = 0; i <= kk; i++)
        cout << c1[i] << ' ';
    cout << endl;*/

    for (pii x : qr[v]) {
        if (ans[x.S])
            continue;
        if (c1[kk-x.F])
            ans[x.S] = true;
        /*else
            for (int i = 1; i < Y; i++)
                if (c2[i] && (kk-x.F) % i == 0)
                    ans[x.S] = true;*/
    }

    for (int u : ch[v])
        dfs2(u);

    for (ll x : a1[v])
        c1[x]--;
    for (ll x : a2[v])
        c2[x]--;
}

void dfs3(int v, ll w) {
    w += wt[v];
    ds[v] = w;

    for (int u : ch[v])
        dfs3(u, w);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> nn >> mm >> kk >> ss;
    ss++;
    pr[0] = -1;

    for (int i = 1; i <= nn; i++) {
        cin >> pr[i] >> wt[i];
        wt[i]++;
        ch[pr[i]].pb(i);
    }

    dfs3(0, 0);
    for (int i = 0; i <= nn; i++)
        if (ds[i] < K)
            ad[ds[i]] = true;

    for (int i = 0; i < mm; i++) {
        int v, l;
        cin >> v >> l;
        qr[v].pb({ds[v]+l+1, i});
    }
    
    for (int i = 0; i <= nn; i++)
        for (pii x : qr[i]) {
            if (x.F == kk) {
                ans[x.S] = true;
                continue;
            }
            int v = i;
            while (v != -1) {
                if (kk+ds[v]-x.F-ss >= 0 && ad[kk+ds[v]-x.F-ss]) {
                    ans[x.S] = true;
                    break;
                }
                v = pr[v];
            }
        }

    dfs2(0);

    for (int i = 0; i < mm; i++)
        cout << (ans[i] ? "YES" : "NO") << endl;
}

Subtask #1
0 / 33.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9152 KB Output is correct
2 Correct 8 ms 8660 KB Output is correct
3 Correct 8 ms 10052 KB Output is correct
4 Correct 8 ms 9556 KB Output is correct
5 Correct 310 ms 82580 KB Output is correct
6 Correct 307 ms 110160 KB Output is correct
7 Correct 162 ms 67624 KB Output is correct
8 Correct 260 ms 87900 KB Output is correct
9 Correct 8 ms 7408 KB Output is correct
10 Correct 6 ms 4052 KB Output is correct
11 Correct 13 ms 6576 KB Output is correct
12 Correct 503 ms 171836 KB Output is correct

Subtask #3
0 / 34.0

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