Submission #343249

#	Time	Username	Problem	Language	Result	Execution time	Memory
343249		FatihSolak	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	100 ms	21868 KiB

catinatree

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl "\n"
#define all(x) (x).begin(), (x).end()
using namespace std;
const int INF = (int) 1e9;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n,d;
vector<int> adj[MAXN];
int ans;
int calc(int v,int par){
    int cnt = 0;
    int tmp = v;
    while(adj[v].size() + (v==0) ==2){
        cnt++;
        for(auto u:adj[v]){
            if(u != par){
                par = v;
                v = u;
                break;
            }
        }
    }
    if((adj[v].size()+(v==0)) == 1){
        ans+=cnt/d+1;
        return cnt%d;
    }
    vector<int> nums;
    for(auto u:adj[v]){
        if(u != par){
            nums.push_back(calc(u,v)+1);
        }
    }
    sort(all(nums));
    reverse(all(nums));
    for(int i=1;i<nums.size();i++){
        if(nums[i]+nums[i-1]<d){
            ans-=(nums.size()-i);
            int ret = cnt+nums[i-1];
            ans+=ret/d;
            return ret%d;
        }
    }
    int ret = cnt+nums[nums.size()-1];
    ans+=ret/d;
    return ret%d;
}
void solve(){
    cin >> n >> d;
    for(int i=0;i<n-1;i++){
        int a;
        cin >> a;
        adj[a].push_back(i+1);
        adj[i+1].push_back(a);
    }
    calc(0,-1);
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message (stderr)

catinatree.cpp: In function 'int calc(int, int)':
catinatree.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=1;i<nums.size();i++){
      |                 ~^~~~~~~~~~~~
catinatree.cpp:20:9: warning: unused variable 'tmp' [-Wunused-variable]
   20 |     int tmp = v;
      |         ^~~

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