Submission #645268

#	Time	Username	Problem	Language	Result	Execution time	Memory
645268		Vu_CG_Coder	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	594 ms	40724 KiB

catinatree

/* [Author : Hoang Duy Vu] - THPT Chuyen Nguyen Du    */
/* [2022 - 12TH GO VOI 23] - From Nguyen Du with love */
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <cmath>
#include <cstdio> 
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <iomanip>
#include <numeric>
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
#define FORE(i,b, a) for(int i = (b), _a = (a); i >= _a; i--)
#define All(x) (x).begin(),(x).end()
#define __ZuyVuNee int main()
#define MASK(i) (1ll<<(i))
#define ll long long
#define se second
#define C make_pair
#define fi first
#define two second.first
#define thr second.second
#define TASK "txt"
using namespace std;

template<typename T> bool maximize(T &res, const T &val) { if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val) { res = val; return true; } return false; }


typedef pair<int,int> ii;
typedef pair<int,ii> iii;
const int LOG = 17;
const int INF = 1e9 + 7;
const ll LNF = 1e18 + 7;
const int mod = 1e9 + 7;
const int N = 200100;

int n , k;
int par[N][LOG + 2];
int high[N];
int Pa[N] = {0};
int cnt[N] = {0};
int f[N] = {0};
int Mn[N] = {0};
ii H[N];

vector <int> a[N];

void findhigh(int u)
{
    for (int v : a[u])
    if (v != par[u][0])
    {
        high[v] = high[u] + 1;
        H[v] = C(high[v],v);
        par[v][0] = u;
        findhigh(v);
    }
}

void write()
{
    cin >> n >> k;
    for (int i = 2; i <= n ; i++)
    {
        int x;
        cin >> x;
        x++;
        a[x].push_back(i);
        a[i].push_back(x);
    }
}

int get(int u , int v)
{
    if (high[u] < high[v]) return get(v,u);

    for (int i = LOG ; i >= 0 ; i--)
    if (high[par[u][i]] >= high[v]) u = par[u][i];

    if (u == v) return u;

    for (int i = LOG ; i >= 0 ; i--)
    if (par[u][i] != par[v][i])
    {
        u = par[u][i];
        v = par[v][i];
    }

    return par[u][0];
}

void subtree(int u , int P)
{
    cnt[u] = 1;

    for (int v : a[u])
    if (v != P && !f[v]) 
    {
        subtree(v,u);
        cnt[u] += cnt[v];
    }
}

int FindCentroid(int u , int P , int t)
{
    for (int v : a[u])
    if (!f[v] && v != P) 
        if (cnt[v]*2 > t) return FindCentroid(v,u,t);
    return u;
}

void Centroid(int u , int P)
{
    subtree(u,u);

    int root = FindCentroid(u,u,cnt[u]);

    Pa[root] = P;

    f[root] = 1;

    for (int v : a[root])
    if (!f[v]) Centroid(v,root);
}


void update(int u)
{
    int x = u;
    while (x)
    {
        minimize(Mn[x],high[u] + high[x] - 2*high[get(u,x)]);
        x = Pa[x];
    }
}

int getMin(int u)
{
    int x = u;
    int res = INF;
    while (x)
    {
        minimize(res,high[u] + high[x] - 2*high[get(u,x)] + Mn[x]);
        x = Pa[x];
    }

    return res;
}

void solve()
{
    high[0] = -1;
    high[1] = 0;
    H[1] = C(0,1);
    par[1][0] = 0;
    findhigh(1);

    for (int j = 1 ; j <= LOG ; j++)
        for (int i = 1 ; i <= n ; i++)
            par[i][j] = par[par[i][j - 1]][j - 1];
    
    Centroid(1,0);

    memset(Mn,0x3f,sizeof(Mn));

    sort(H + 1 , H + n + 1,greater<ii>());

    int res = 1;
    update(H[1].se);

    for (int i = 2 ; i <= n ; i++)
    {
        int x = H[i].fi;
        int y = H[i].se;
       if (getMin(y) >= k) 
       {
            update(y);
            res++;
       }
    }

    cout << res;
}

__ZuyVuNee
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    if(fopen(TASK".inp", "r")){
    freopen(TASK".inp","r",stdin);
    freopen(TASK".out","w",stdout);
    }

    int tk;
    tk = 1;
   //cin >> tk;
    while (tk)
    {
        tk--;
        write();
        solve();
    }
    return 0;
}

Compilation message (stderr)

catinatree.cpp: In function 'void solve()':
catinatree.cpp:182:13: warning: unused variable 'x' [-Wunused-variable]
  182 |         int x = H[i].fi;
      |             ^
catinatree.cpp: In function 'int main()':
catinatree.cpp:199:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  199 |     freopen(TASK".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
catinatree.cpp:200:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  200 |     freopen(TASK".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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