oj.uz

Submission #343178

# Submission time Handle Problem Language Result Execution time Memory
343178 2021-01-03T13:15:16 Z FatihSolak Cat in a tree (BOI17_catinatree) C++17
0 / 100
 5 ms 7404 KB 
#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 now = v;
    int cnt = 0;
    int tmp = par;
    while(adj[now].size()<=(2-(now==0))){
        cnt++;
        for(auto u:adj[now]){
            if(u != tmp){
                tmp = now;
                now = u;
                break;
            }
        }
        if((adj[now].size()+(now==0)) == 1){
            ans+=cnt/d;
            return cnt%d;
        }
    }
    vector<int> nums;
    for(auto u:adj[now]){
        if(u != tmp){
            nums.push_back(calc(u,now)+1);
        }
    }
    sort(all(nums));
    reverse(all(nums));
    int last = nums[0];
    for(int i=0;i<nums.size();i++){
        if(nums[i]+last<d){
            break;
        }
        else{
            ans++;
            last = nums[i]; 
        }
    }
    return cnt+last;

}
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 << max(1,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

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7404 KB Output isn't correct
2 Halted 0 ms 0 KB -