Submission #799589

#	Time	Username	Problem	Language	Result	Execution time	Memory
799589		winthemcut3	Cat in a tree (BOI17_catinatree)	C++14	0 / 100	2 ms	4948 KiB

catinatree

#include <bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define PB push_back
#define ALL(v) (v).begin(), (v).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define fi   first
#define se   second
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;

/** END OF TEMPLATE **/

const int mxN = 2e5 + 5;
typedef pair<int, int> pii;
int n, k;
vector<int> g[mxN];

int f[mxN], d[mxN];
void dfs(int u, int par) {
    f[u] = 1;
    vector<int> t{0};
    for(int &v : g[u]) {
        if(v == par) continue;
        dfs(v, u);
        t.PB(d[v]);
        f[u] += f[v];
    }
    sort(ALL(t));
    int pos = t.size() - 1;
    for(int i = 0; i < t.size()-2; ++i)
        if(t[i] + t[i+1] < k) f[u]--;
        else {
            pos = i;
            break;
        }
    d[u] = t[pos] + 1;
}
int main()
{
    FastIO;
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    cin >> n >> k;
    FOR(i, 2, n) {
        int x; cin >> x;
        g[i].PB(x+1); g[x+1].PB(i);
    }
    dfs(1, 0);
    cout << f[1];
    return 0;
}

/*

*/

Compilation message (stderr)

catinatree.cpp: In function 'void dfs(int, int)':
catinatree.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i = 0; i < t.size()-2; ++i)
      |                    ~~^~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 40
• Subtask 3: 0 / 49