Submission #883814

#	Time	Username	Problem	Language	Result	Execution time	Memory
883814		imarn	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	267 ms	249816 KiB

catinatree

#include<bits/stdc++.h>
#define pii pair<long long,int>
#define f first
#define pb push_back
#define s second
using namespace std;
const int N=2e5+5;
vector<int>g[N];
deque<int>dq[N];
int ans=0;
int k;
void dfs(int u=0,int p=0){
    dq[u].pb(1);
    for(auto v:g[u]){
        if(v==p)continue;
        dfs(v,u);dq[v].push_front(dq[v].front());
        if(dq[v].size()>dq[u].size())swap(dq[u],dq[v]);
        deque<int>x;
        for(int i=0;i<dq[v].size();i++){
            int a=max(k-i,i);x.pb(dq[v][i]);
            if(a<dq[u].size())x[i]=max(x[i],dq[v][i]+dq[u][a]);
            if(a<dq[v].size())x[i]=max(x[i],dq[v][a]+dq[u][i]);
        }int mx=0;
        for(int i=(int)dq[v].size()-1;i>=0;i--){
            mx=max(mx,x[i]);
            dq[u][i] = max(dq[u][i],mx);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n>>k;
    for(int i=1,u;i<=n-1;i++)cin>>u,g[u].pb(i),g[i].pb(u);
    dfs();cout<<dq[0].front();
}

Compilation message (stderr)

catinatree.cpp: In function 'void dfs(int, int)':
catinatree.cpp:19:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         for(int i=0;i<dq[v].size();i++){
      |                     ~^~~~~~~~~~~~~
catinatree.cpp:21:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |             if(a<dq[u].size())x[i]=max(x[i],dq[v][i]+dq[u][a]);
      |                ~^~~~~~~~~~~~~
catinatree.cpp:22:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |             if(a<dq[v].size())x[i]=max(x[i],dq[v][a]+dq[u][i]);
      |                ~^~~~~~~~~~~~~

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