oj.uz

Submission #698868

# Submission time Handle Problem Language Result Execution time Memory
698868 2023-02-14T14:17:37 Z _martynas Cat in a tree (BOI17_catinatree) C++11
100 / 100
 676 ms 73796 KB 
#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;
using vi = vector<int>;

#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

const int MXN = 2e5+5;

int n, D;
int P[MXN];
vi adj[MXN];
int depth[MXN];
// centroid
int id = 0;
int level[MXN], par[MXN], where[MXN], sz[MXN];
int dist[25][MXN];
vector<vector<pii>> components;
bool visited[MXN];

void dfs(int u, int p) {
    sz[u] = 1;
    for(int v : adj[u]) if(v != p && !level[v]) {
        dfs(v, u);
        sz[u] += sz[v];
    }
}

int centroid(int u, int p, int tree_sz) {
    for(int v : adj[u]) if(v != p && !level[v]) {
        if(2*sz[v] > tree_sz) {
            return centroid(v, u, tree_sz);
        }
    }
    return u;
}

void set_dist(int u, int p, int lvl, int d) {
    dist[lvl][u] = d;
    for(int v : adj[u]) if(v != p && !level[v]) {
        set_dist(v, u, lvl, d+1);
    }
}

void get_comp(int u, int p, vi &comp) {
    comp.PB(u);
    for(int v : adj[u]) if(v != p && !level[v]) {
        get_comp(v, u, comp);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> D;
    for(int i = 1; i < n; i++) {
        cin >> P[i];
        adj[P[i]].PB(i);
        adj[i].PB(P[i]);
    }
    fill(par, par+n, -1);
    int lvl = 1;
    while(id < n) {
        if(id == 0) {
            dfs(0, -1);
            int c = centroid(0, -1, n);
            level[c] = lvl;
            set_dist(c, -1, lvl, 0);
            vi comp; get_comp(c, -1, comp);
            assert(comp.size() == n);
            for(int u : comp) if(u != c) par[u] = c;
            vector<pii> comp_with_dist;
            for(int u : comp) comp_with_dist.PB({dist[lvl][u], u});
            sort(rall(comp_with_dist));
            components.PB(comp_with_dist);
            where[c] = id++;
        }
        else {
            for(int u = 0; u < n; u++) if(level[u] == lvl-1) {
                for(int v : adj[u]) if(!level[v]) {
                    dfs(v, -1);
                    int c = centroid(v, -1, sz[v]);
                    level[c] = lvl;
                    set_dist(c, -1, lvl, 0);
                    vi comp; get_comp(c, -1, comp);
                    for(int i : comp) if(i != c) par[i] = c;
                    vector<pii> comp_with_dist;
                    for(int i : comp) comp_with_dist.PB({dist[lvl][i], i});
                    sort(rall(comp_with_dist));
                    components.PB(comp_with_dist);
                    where[c] = id++;
                }
            }
        }
        lvl++;
    }
//    for(int i = 0; i < id; i++) {
//        cerr << i << ":\n";
//        cerr << "vertices:\n";
//        for(auto p : components[i]) cerr << p.S << " ";
//        cerr << "\n";
//        cerr << "distance from " << components[i].back().S << ":\n";
//        for(auto p : components[i]) cerr << p.F << " ";
//        cerr << "\n";
//    }
    vi order;
    // decreasing distance order from full tree centroid
    for(auto p : components[0]) {
        order.PB(p.S);
    }
    int ans = 0;
    for(int i : order) {
        if(visited[i]) continue;
        visited[i] = true;
        ans++;
        int j = i;
        while(j != -1) {
            int c = where[j];
            while(!components[c].empty() && components[c].back().F + dist[level[j]][i] < D) {
                visited[components[c].back().S] = true;
                components[c].pop_back();
            }
            j = par[j];
        }
    }
    cout << ans << "\n";
    return 0;
}

/*
6 4
0
1
2
2
4

*/

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from catinatree.cpp:1:
catinatree.cpp: In function 'int main()':
catinatree.cpp:75:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |             assert(comp.size() == n);
      |                    ~~~~~~~~~~~~^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 4 ms 5076 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 4 ms 5076 KB Output is correct
14 Correct 3 ms 5008 KB Output is correct
15 Correct 4 ms 5048 KB Output is correct
16 Correct 3 ms 5040 KB Output is correct
17 Correct 3 ms 5076 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 3 ms 5076 KB Output is correct
20 Correct 2 ms 5076 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 4 ms 5076 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 4 ms 5076 KB Output is correct
14 Correct 3 ms 5008 KB Output is correct
15 Correct 4 ms 5048 KB Output is correct
16 Correct 3 ms 5040 KB Output is correct
17 Correct 3 ms 5076 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 3 ms 5076 KB Output is correct
20 Correct 2 ms 5076 KB Output is correct
21 Correct 5 ms 5588 KB Output is correct
22 Correct 4 ms 5076 KB Output is correct
23 Correct 3 ms 5168 KB Output is correct
24 Correct 3 ms 5172 KB Output is correct
25 Correct 4 ms 5304 KB Output is correct
26 Correct 4 ms 5204 KB Output is correct
27 Correct 4 ms 5304 KB Output is correct
28 Correct 4 ms 5332 KB Output is correct
29 Correct 4 ms 5332 KB Output is correct
30 Correct 4 ms 5332 KB Output is correct
31 Correct 6 ms 5332 KB Output is correct
32 Correct 4 ms 5332 KB Output is correct
33 Correct 3 ms 5300 KB Output is correct
34 Correct 3 ms 5332 KB Output is correct
35 Correct 4 ms 5332 KB Output is correct
36 Correct 4 ms 5388 KB Output is correct
37 Correct 4 ms 5300 KB Output is correct
38 Correct 5 ms 5460 KB Output is correct
39 Correct 5 ms 5460 KB Output is correct
40 Correct 5 ms 5588 KB Output is correct

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 4 ms 5076 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 4 ms 5076 KB Output is correct
14 Correct 3 ms 5008 KB Output is correct
15 Correct 4 ms 5048 KB Output is correct
16 Correct 3 ms 5040 KB Output is correct
17 Correct 3 ms 5076 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 3 ms 5076 KB Output is correct
20 Correct 2 ms 5076 KB Output is correct
21 Correct 5 ms 5588 KB Output is correct
22 Correct 4 ms 5076 KB Output is correct
23 Correct 3 ms 5168 KB Output is correct
24 Correct 3 ms 5172 KB Output is correct
25 Correct 4 ms 5304 KB Output is correct
26 Correct 4 ms 5204 KB Output is correct
27 Correct 4 ms 5304 KB Output is correct
28 Correct 4 ms 5332 KB Output is correct
29 Correct 4 ms 5332 KB Output is correct
30 Correct 4 ms 5332 KB Output is correct
31 Correct 6 ms 5332 KB Output is correct
32 Correct 4 ms 5332 KB Output is correct
33 Correct 3 ms 5300 KB Output is correct
34 Correct 3 ms 5332 KB Output is correct
35 Correct 4 ms 5332 KB Output is correct
36 Correct 4 ms 5388 KB Output is correct
37 Correct 4 ms 5300 KB Output is correct
38 Correct 5 ms 5460 KB Output is correct
39 Correct 5 ms 5460 KB Output is correct
40 Correct 5 ms 5588 KB Output is correct
41 Correct 137 ms 33296 KB Output is correct
42 Correct 269 ms 28496 KB Output is correct
43 Correct 243 ms 28620 KB Output is correct
44 Correct 229 ms 28704 KB Output is correct
45 Correct 215 ms 28448 KB Output is correct
46 Correct 639 ms 52140 KB Output is correct
47 Correct 627 ms 53088 KB Output is correct
48 Correct 676 ms 53300 KB Output is correct
49 Correct 636 ms 53216 KB Output is correct
50 Correct 123 ms 25924 KB Output is correct
51 Correct 148 ms 26384 KB Output is correct
52 Correct 124 ms 25840 KB Output is correct
53 Correct 317 ms 47424 KB Output is correct
54 Correct 320 ms 47028 KB Output is correct
55 Correct 369 ms 47076 KB Output is correct
56 Correct 6 ms 5744 KB Output is correct
57 Correct 32 ms 12444 KB Output is correct
58 Correct 175 ms 41716 KB Output is correct
59 Correct 614 ms 73796 KB Output is correct
60 Correct 139 ms 34420 KB Output is correct
61 Correct 277 ms 43032 KB Output is correct