제출 #1172474

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172474		ElayV13	Cat in a tree (BOI17_catinatree)	C++20	0 / 100	2 ms	4928 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define FOR(a , b) for(int i = a;i <= b;i++)
#define pb push_back

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MXN = 2e5 + 5;
const int INF = 1e18;

int N , D;
vector < int > adj[MXN];

int get_dia()
{
        queue < int > q;
        vector < int > d(N + 1 , INF);
        q.push(1);
        d[1] = 0;
        while(!q.empty())
        {
                int v = q.front();
                q.pop();
                for(int u : adj[v]){
                        if(d[u] == INF){
                                d[u] = d[v] + 1;
                                q.push(u);
                        }
                }
        }
        int mx = -1 , node = -1;
        for(int i = 1;i <= N;i++){
                if(d[i] > mx)
                {
                        node = i;
                        mx = d[i];
                }
        }
        q = {};
        d.assign(N + 1 , INF);
        q.push(node);
        d[node] = 0;
        while(!q.empty())
        {
                int v = q.front();
                q.pop();
                for(int u : adj[v]){
                        if(d[u] == INF){
                                d[u] = d[v] + 1;
                                q.push(u);
                        }
                }
        }
        mx = -1;
        for(int i = 1;i <= N;i++) mx = max(mx , d[i]);
        return mx;
}

void solve()
{
        cin >> N >> D;
        for(int i = 2;i <= N;i++)
        {
                int u;
                cin >> u;
                ++u;
                adj[i].push_back(u);
                adj[u].push_back(i);
        }
        int d = get_dia();
        cout << d / D + 1 << endl;
}

signed main(){
      ios_base::sync_with_stdio(0);cin.tie(0);
      int T = 1;
      //cin >> T;
      FOR(1 , T) solve();
}

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