oj.uz

Submission #469464

# Submission time Handle Problem Language Result Execution time Memory
469464 2021-09-01T04:37:46 Z sumit_kk10 Cat in a tree (BOI17_catinatree) C++14
11 / 100
 1000 ms 149148 KB 
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define ld long double
using namespace std;
const int N = 1e6 + 5;
const int MOD = 1e9 + 7;
ll dp[N][(ll) log2(100005)], n, d, lvl[N];
vector<int> graph[N];

void dfs(int source, int par, int level){
    dp[source][0] = par;
    lvl[source] = level;
    for(auto k : graph[source])
        if(k != par)
            dfs(k, source, level + 1);
}

void init(){
    dfs(0, -1, 0);
    for(int i = 1; i <= (log2(n)); ++i)
        for(int j = 0; j < n; ++j)
            if(dp[j][i - 1] != -1)
                dp[j][i] = dp[dp[j][i - 1]][i - 1];
}

ll LCA(int u, int v){
    if(lvl[u] > lvl[v]) swap(u, v);
    ll d = lvl[v] - lvl[u];
    while(d){
        int jump = log2(d);
        v = dp[v][jump];
        d -= pow(2, jump);
    }
    if(v == u) 
        return v;
    for(int i = log2(n); i >= 0; --i){
        if(dp[v][i] != -1 && dp[v][i] != dp[u][i]){
            u = dp[u][i];
            v = dp[v][i];
        }
    }
    return dp[v][0];
}

void solve(){
    cin >> n >> d;
    for(int i = 1; i < n; ++i){
        int p;
        cin >> p;
        graph[p].push_back(i);
        graph[i].push_back(p);
    }
    memset(dp, -1, sizeof dp);
    init();
    int ans = 0;
    for(int i = 0; i < (1 << n); ++i){
        vector<int> nodes;
        for(int j = 0; j < n; ++j){
            if(i & (1 << j))
                nodes.push_back(j);
        }
        bool ok = 1;
        for(int j = 0; j < nodes.size(); ++j){
            for(int k = j + 1; k < nodes.size(); ++k){
                int p = LCA(nodes[j], nodes[k]);
                ll dis = lvl[nodes[j]] + lvl[nodes[k]] - 2*lvl[p];
                if(dis < d){
                    ok = 0;
                    break;
                }
            }
            if(!ok) break;
        }
        if(ok) ans = max(ans, (int) nodes.size());
    }
    cout << ans << "\n";
}

int main(){
    fast;
    int t = 1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
    // you should actually read the stuff at the bottom
}
/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
    * Read other problems if stuck on this one.
*/

Compilation message

catinatree.cpp: In function 'void solve()':
catinatree.cpp:64:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int j = 0; j < nodes.size(); ++j){
      |                        ~~^~~~~~~~~~~~~~
catinatree.cpp:65:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             for(int k = j + 1; k < nodes.size(); ++k){
      |                                ~~^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 148924 KB Output is correct
2 Correct 64 ms 148924 KB Output is correct
3 Correct 70 ms 148944 KB Output is correct
4 Correct 66 ms 148932 KB Output is correct
5 Correct 81 ms 148932 KB Output is correct
6 Correct 72 ms 148948 KB Output is correct
7 Correct 94 ms 149000 KB Output is correct
8 Correct 85 ms 149032 KB Output is correct
9 Correct 694 ms 149028 KB Output is correct
10 Correct 141 ms 148920 KB Output is correct
11 Correct 481 ms 148940 KB Output is correct
12 Correct 378 ms 149032 KB Output is correct
13 Correct 339 ms 149032 KB Output is correct
14 Correct 127 ms 149028 KB Output is correct
15 Correct 139 ms 148976 KB Output is correct
16 Correct 737 ms 149044 KB Output is correct
17 Correct 172 ms 148932 KB Output is correct
18 Correct 144 ms 149028 KB Output is correct
19 Correct 160 ms 149092 KB Output is correct
20 Correct 149 ms 148980 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 148924 KB Output is correct
2 Correct 64 ms 148924 KB Output is correct
3 Correct 70 ms 148944 KB Output is correct
4 Correct 66 ms 148932 KB Output is correct
5 Correct 81 ms 148932 KB Output is correct
6 Correct 72 ms 148948 KB Output is correct
7 Correct 94 ms 149000 KB Output is correct
8 Correct 85 ms 149032 KB Output is correct
9 Correct 694 ms 149028 KB Output is correct
10 Correct 141 ms 148920 KB Output is correct
11 Correct 481 ms 148940 KB Output is correct
12 Correct 378 ms 149032 KB Output is correct
13 Correct 339 ms 149032 KB Output is correct
14 Correct 127 ms 149028 KB Output is correct
15 Correct 139 ms 148976 KB Output is correct
16 Correct 737 ms 149044 KB Output is correct
17 Correct 172 ms 148932 KB Output is correct
18 Correct 144 ms 149028 KB Output is correct
19 Correct 160 ms 149092 KB Output is correct
20 Correct 149 ms 148980 KB Output is correct
21 Execution timed out 1093 ms 149148 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 148924 KB Output is correct
2 Correct 64 ms 148924 KB Output is correct
3 Correct 70 ms 148944 KB Output is correct
4 Correct 66 ms 148932 KB Output is correct
5 Correct 81 ms 148932 KB Output is correct
6 Correct 72 ms 148948 KB Output is correct
7 Correct 94 ms 149000 KB Output is correct
8 Correct 85 ms 149032 KB Output is correct
9 Correct 694 ms 149028 KB Output is correct
10 Correct 141 ms 148920 KB Output is correct
11 Correct 481 ms 148940 KB Output is correct
12 Correct 378 ms 149032 KB Output is correct
13 Correct 339 ms 149032 KB Output is correct
14 Correct 127 ms 149028 KB Output is correct
15 Correct 139 ms 148976 KB Output is correct
16 Correct 737 ms 149044 KB Output is correct
17 Correct 172 ms 148932 KB Output is correct
18 Correct 144 ms 149028 KB Output is correct
19 Correct 160 ms 149092 KB Output is correct
20 Correct 149 ms 148980 KB Output is correct
21 Execution timed out 1093 ms 149148 KB Time limit exceeded
22 Halted 0 ms 0 KB -