oj.uz

답안 #734531

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
734531 2023-05-02T15:21:49 Z Victor Cat in a tree (BOI17_catinatree) C++17
0 / 100
 5 ms 5028 KB 
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (ll i = (a); i < (b); ++i)
#define per(i, a, b) for (ll i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) (ll)x.size()
#define pb push_back
#define mp make_pair
#define debug(x) cout<<#x<<" = "<<x<<endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const ll INF = 1'000'000'007;

vll graph[200005];
ll n,d,maxd,node;
bitset<200005> marked;

void dfs1(ll u,ll p, ll curd) {
    if(!marked[u]&&curd>maxd) node=u;
    trav(v,graph[u]) if(v!=p) dfs1(v,u,curd+1);
}

void dfs2(ll u,ll p,ll curd) {
    if(curd==d) return;
    marked[u]=1;
    trav(v,graph[u]) if(v!=p) dfs2(v,u,curd+1);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    cin>>n>>d;
    rep(i,1,n) {
        ll p;
        cin>>p;
        graph[p].pb(i);
        graph[i].pb(p);
    }

    ll ans=0;
    while(true) {
        maxd=-1;
        node=-1;
        dfs1(0,0,0);
        if(node==-1) break;

        dfs2(node,node,0);
        ++ans;
    }

    cout<<ans<<endl;
    return 0;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 5 ms 4948 KB Output is correct
5 Correct 4 ms 4948 KB Output is correct
6 Correct 3 ms 5020 KB Output is correct
7 Correct 4 ms 5028 KB Output is correct
8 Correct 5 ms 5024 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Incorrect 3 ms 4948 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 5 ms 4948 KB Output is correct
5 Correct 4 ms 4948 KB Output is correct
6 Correct 3 ms 5020 KB Output is correct
7 Correct 4 ms 5028 KB Output is correct
8 Correct 5 ms 5024 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Incorrect 3 ms 4948 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 5 ms 4948 KB Output is correct
5 Correct 4 ms 4948 KB Output is correct
6 Correct 3 ms 5020 KB Output is correct
7 Correct 4 ms 5028 KB Output is correct
8 Correct 5 ms 5024 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Incorrect 3 ms 4948 KB Output isn't correct
11 Halted 0 ms 0 KB -