Submission #1108219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108219		0pt1mus23	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	120 ms	99912 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 2e5 +10, inf = INT_MAX, LL = 30;

int n,k;
int val[sze];
vector<int> graph[sze];
deque<int> dfs(int node,int par=-1){
    deque<int> res;
    res.pb(1);
    for(auto v:graph[node]){
        if(v!=par){
            auto nxt = dfs(v,node);
            nxt.push_front(0);
            if(nxt.size()>res.size()){
                swap(nxt,res);
            }
            for(int j=0;j<nxt.size();j++){
                int y = max(j,k-j);
                int a = nxt[j] + (y<res.size() ?  res[y] : 0);
                int b = res[j] + (y<nxt.size() ? nxt[y] : 0) ;
                res[j]=max({res[j],a,b});
            }
            for(int j = nxt.size()-1;j>=0;j--){
                if(j+1<res.size()){
                    res[j]=max(res[j],res[j+1]);
                }
            }
        }
    }
    return res;
}
void rush(){
    cin>>n>>k;
    for(int i=2;i<=n;i++){
        int u;cin>>u;
        int v=i;
        ++u;
        graph[u].pb(v);
        graph[v].pb(u);
    }
    deque<int> res = dfs(1,0);
    cout<<res[0]<<endl;
}
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tt = 1; 
    // cin>>tt;
 
    while(tt--){
        rush();
    }
 
    return 0;
}

Compilation message (stderr)

catinatree.cpp: In function 'std::deque<long long int> dfs(long long int, long long int)':
catinatree.cpp:24:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |             for(int j=0;j<nxt.size();j++){
      |                         ~^~~~~~~~~~~
catinatree.cpp:26:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |                 int a = nxt[j] + (y<res.size() ?  res[y] : 0);
      |                                   ~^~~~~~~~~~~
catinatree.cpp:27:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |                 int b = res[j] + (y<nxt.size() ? nxt[y] : 0) ;
      |                                   ~^~~~~~~~~~~
catinatree.cpp:31:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |                 if(j+1<res.size()){
      |                    ~~~^~~~~~~~~~~

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