oj.uz

Submission #553467

# Submission time Handle Problem Language Result Execution time Memory
553467 2022-04-25T23:20:22 Z Talha_Taki Cat in a tree (BOI17_catinatree) C++17
51 / 100
 1000 ms 45376 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
 
typedef long long ll;
typedef pair <int, int> pii;
 
vector <vector <int>> adj, parent;
vector <int> tin, tout, depth;
set <pii, greater <pii>> S;

int k, timer;

void dfs(int u, int p, int d) {
    depth[u] = d;
    tin[u] = ++timer;

    S.insert({d, u});
    for(int i = 1; i <= k; ++i) parent[u][i] = parent[parent[u][i-1]][i-1];
    for(int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u, d+1);
    }

    tout[u] = ++timer;
}

inline bool isAncestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v) {
    if (isAncestor(u, v)) return u;
    if (isAncestor(v, u)) return v;

    for(int i = k; i >= 0; --i) {
        if (!isAncestor(parent[u][i], v)) {
            u = parent[u][i];
        }
    }

    return parent[u][0];
}

int dist(int a, int b) {
    return depth[a] + depth[b] - (depth[lca(a, b)]<<1);
}
 
int main(const int argc, const char *argv[]) {
 
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, d;
    cin >> n >> d;

    k = ceil(log2(n));
    adj.resize(n+1);
    parent.assign(n+1, vector <int> (k+1, 0));
    tin.resize(n+1);
    tout.resize(n+1);
    depth.resize(n+1);

    tin[0] = 0;
    tout[0] = n<<2|1;

    for(int i = 2; i <= n; ++i) {
        int p;
        cin >> p;
        ++p;

        parent[i][0] = p;
        adj[i].push_back(parent[i][0]);
        adj[parent[i][0]].push_back(i);
    }
    dfs(1, 0, 0);

    int ans = 0;
    while (!S.empty()) {
        auto u = (*S.begin()).second;
        ans++;

        for(int i = 1; i <= n; ++i) {
            if (dist(u, i) < d) {
                S.erase({depth[i], i});
            }
        }
    }


    cout << ans;

 
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 324 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 316 KB Output is correct
19 Correct 1 ms 320 KB Output is correct
20 Correct 0 ms 316 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 324 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 316 KB Output is correct
19 Correct 1 ms 320 KB Output is correct
20 Correct 0 ms 316 KB Output is correct
21 Correct 2 ms 724 KB Output is correct
22 Correct 6 ms 340 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 1 ms 324 KB Output is correct
25 Correct 24 ms 524 KB Output is correct
26 Correct 5 ms 468 KB Output is correct
27 Correct 3 ms 444 KB Output is correct
28 Correct 4 ms 596 KB Output is correct
29 Correct 13 ms 724 KB Output is correct
30 Correct 3 ms 596 KB Output is correct
31 Correct 2 ms 596 KB Output is correct
32 Correct 2 ms 596 KB Output is correct
33 Correct 1 ms 596 KB Output is correct
34 Correct 2 ms 596 KB Output is correct
35 Correct 2 ms 596 KB Output is correct
36 Correct 2 ms 596 KB Output is correct
37 Correct 4 ms 580 KB Output is correct
38 Correct 2 ms 596 KB Output is correct
39 Correct 2 ms 596 KB Output is correct
40 Correct 3 ms 724 KB Output is correct

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 324 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 316 KB Output is correct
19 Correct 1 ms 320 KB Output is correct
20 Correct 0 ms 316 KB Output is correct
21 Correct 2 ms 724 KB Output is correct
22 Correct 6 ms 340 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 1 ms 324 KB Output is correct
25 Correct 24 ms 524 KB Output is correct
26 Correct 5 ms 468 KB Output is correct
27 Correct 3 ms 444 KB Output is correct
28 Correct 4 ms 596 KB Output is correct
29 Correct 13 ms 724 KB Output is correct
30 Correct 3 ms 596 KB Output is correct
31 Correct 2 ms 596 KB Output is correct
32 Correct 2 ms 596 KB Output is correct
33 Correct 1 ms 596 KB Output is correct
34 Correct 2 ms 596 KB Output is correct
35 Correct 2 ms 596 KB Output is correct
36 Correct 2 ms 596 KB Output is correct
37 Correct 4 ms 580 KB Output is correct
38 Correct 2 ms 596 KB Output is correct
39 Correct 2 ms 596 KB Output is correct
40 Correct 3 ms 724 KB Output is correct
41 Execution timed out 1091 ms 45376 KB Time limit exceeded
42 Halted 0 ms 0 KB -