oj.uz

Submission #883813

# Submission time Handle Problem Language Result Execution time Memory
883813 2023-12-06T06:27:17 Z imarn Cat in a tree (BOI17_catinatree) C++14
0 / 100
 64 ms 139604 KB 
#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]);
        }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

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]);
      |                ~^~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 139604 KB Output is correct
2 Incorrect 64 ms 139600 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 139604 KB Output is correct
2 Incorrect 64 ms 139600 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 139604 KB Output is correct
2 Incorrect 64 ms 139600 KB Output isn't correct
3 Halted 0 ms 0 KB -