/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 8ms 9.266 MiB
#2 Accepted 6ms 8.527 MiB
#3 Accepted 8ms 13.172 MiB
#4 Accepted 10ms 16.273 MiB
#5 Accepted 314ms 65.953 MiB
#6 Accepted 342ms 61.949 MiB
#7 Accepted 218ms 30.004 MiB
#8 Accepted 419ms 48.109 MiB
#9 Accepted 184ms 23.98 MiB
#10 Accepted 664ms 69.992 MiB
#11 Accepted 753ms 77.93 MiB
#12 Accepted 970ms 90.062 MiB
#13 Accepted 744ms 79.422 MiB
#14 Accepted 217ms 14.605 MiB
#15 Accepted 300ms 27.324 MiB
#16 Accepted 658ms 73.41 MiB
#17 Accepted 265ms 17.305 MiB
#18 Accepted 641ms 69.398 MiB
#19 Accepted 375ms 85.258 MiB
#20 Accepted 454ms 92.375 MiB
#21 Accepted 306ms 71.496 MiB
#22 Accepted 20ms 54.332 MiB
#23 Accepted 27ms 79.777 MiB
#24 Accepted 9ms 13.812 MiB

Code

/*
 *   Copyright (c) 2024 Emon Thakur
 *   All rights reserved.
 */
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
vector<int> g[200005];
int height[200005] , dp[101][200005];
int n,k;

#define fr freopen("input19.txt","r",stdin);
ofstream file("output19.txt");

void dfs(int node,int par)
{
    height[node] = 0;
    for(int e:g[node])
    {
        if(e==par) continue;
        dfs(e,node);
    }
    int mx = 0;
    for(int e:g[node])
    {
        if(e==par) continue;
        mx = max(mx , height[e]);
    }
    height[node] = mx+1;
}

void dpontree(int node,int par)
{
    int mxh=0,mxh2=0;
    for(auto e:g[node])
    {
        if(e==par) continue;
        if(height[e] >= mxh)
        {
            mxh2 = mxh;
            mxh = height[e];
        }
        else if(height[e] > mxh2) mxh2 = height[e];
    }
    
    for(auto e:g[node])
    {
        if(e==par) continue;
        dpontree(e,node);
    }

    for(int i=0;i<=k;i++)
    {
        dp[i][node] = 1;
        for(auto e:g[node])
        {
            if(e==par) continue;
            if(height[e] == mxh)
            {
                dp[i][node] = max(dp[i][node] , min(mxh2,i) + dp[max(0,i-mxh2)][e] + 1);
            }
            else 
            {
                dp[i][node] = max(dp[i][node] , min(mxh,i) + dp[max(0,i-mxh)][e] + 1);
            }
        }
    }
}


int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    //fr
    cin >> n >> k;
    for(int i=0;i<n-1;i++)
    {
        int u,v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    //for(int i=1;i<=n;i++) cout<<i<<" "<<height[i]<<endl;
    dpontree(1,0);
    cout << dp[k][1] << endl;
    //file<<dp[k][1]<<endl;
    //for(int i=0;i<=k;i++) cout<<i<<" "<<dp[i][1]<<endl;
}

Information

Submit By
Type
Submission
Problem
P1111 Thakurs tree game
Language
C++17 (G++ 13.2.0)
Submit At
2024-10-09 14:49:45
Judged At
2024-11-11 02:38:07
Judged By
Score
100
Total Time
970ms
Peak Memory
92.375 MiB