oj.uz

Submission #668665

# Submission time Handle Problem Language Result Execution time Memory
668665 2022-12-04T11:16:16 Z mhn2 File Paths (BOI15_fil) C++17
33 / 100
 793 ms 262144 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 = 20, 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
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 852 KB Output is correct
2 Correct 6 ms 2516 KB Output is correct
3 Correct 10 ms 9172 KB Output is correct
4 Correct 69 ms 19708 KB Output is correct
5 Correct 15 ms 10176 KB Output is correct
6 Correct 9 ms 6100 KB Output is correct
7 Correct 16 ms 8532 KB Output is correct
8 Correct 10 ms 5804 KB Output is correct
9 Correct 11 ms 6584 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 6 ms 1748 KB Output is correct
12 Correct 71 ms 22372 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 9144 KB Output is correct
2 Correct 62 ms 8188 KB Output is correct
3 Correct 59 ms 10264 KB Output is correct
4 Correct 71 ms 9680 KB Output is correct
5 Correct 284 ms 79424 KB Output is correct
6 Correct 670 ms 163308 KB Output is correct
7 Correct 222 ms 67928 KB Output is correct
8 Correct 719 ms 134564 KB Output is correct
9 Correct 66 ms 7000 KB Output is correct
10 Correct 77 ms 3916 KB Output is correct
11 Correct 37 ms 21180 KB Output is correct
12 Runtime error 793 ms 262144 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 852 KB Output is correct
2 Correct 6 ms 2516 KB Output is correct
3 Correct 10 ms 9172 KB Output is correct
4 Correct 69 ms 19708 KB Output is correct
5 Correct 15 ms 10176 KB Output is correct
6 Correct 9 ms 6100 KB Output is correct
7 Correct 16 ms 8532 KB Output is correct
8 Correct 10 ms 5804 KB Output is correct
9 Correct 11 ms 6584 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 6 ms 1748 KB Output is correct
12 Correct 71 ms 22372 KB Output is correct
13 Correct 69 ms 9144 KB Output is correct
14 Correct 62 ms 8188 KB Output is correct
15 Correct 59 ms 10264 KB Output is correct
16 Correct 71 ms 9680 KB Output is correct
17 Correct 284 ms 79424 KB Output is correct
18 Correct 670 ms 163308 KB Output is correct
19 Correct 222 ms 67928 KB Output is correct
20 Correct 719 ms 134564 KB Output is correct
21 Correct 66 ms 7000 KB Output is correct
22 Correct 77 ms 3916 KB Output is correct
23 Correct 37 ms 21180 KB Output is correct
24 Runtime error 793 ms 262144 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -