oj.uz

답안 #343237

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
343237 2021-01-03T14:53:25 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 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;
        return cnt%d+(tmp==0);
    }
    vector<int> nums;
    for(auto u:adj[v]){
        if(u != par){
            nums.push_back(calc(u,v)+1);
        }
    }
    sort(all(nums));
    reverse(all(nums));
    ans++;
    for(int i=1;i<nums.size();i++){
        if(nums[i]+nums[i-1]<d){
            int ret = cnt+nums[i-1];
            ans+=ret/d;
            return ret%d;
        }
        ans++;
    }
    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 << max(n/d+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:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=1;i<nums.size();i++){
      |                 ~^~~~~~~~~~~~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 7404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 7404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 7404 KB Output isn't correct
2 Halted 0 ms 0 KB -