제출 #936844

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
936844		asdasdqwer	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	100 ms	24212 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;

#define pii array<int,2>
#define tii array<int,3>

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n,d;cin>>n>>d;
    vector<vector<int>> g(n);
    for (int i=1;i<n;i++) {
        int p;cin>>p;
        g[p].push_back(i);
        g[i].push_back(p);
    }
    
    int ans = 0;
    vector<bool> valid(n, true);
    int validNodes = n;

    vector<pii> depth;
    function<void(int,int,int)> dfs=[&](int node, int pv, int dp) {
        depth.push_back({dp, node});
        for (auto &x:g[node]) {
            if (x == pv)continue;
            dfs(x, node, dp+1);
        }
    };

    dfs(0, -1, 0);
    sort(depth.begin(), depth.end());
    vector<int> dis(n, 1e9);

    while (validNodes) {
        auto [dist, node] = depth.back();
        depth.pop_back();
        if (!valid[node])continue;

        valid[node] = false;
        validNodes--;
        ans++;

        queue<int> q;
        q.push(node);
        dis[node] = 0;

        while (!q.empty()) {
            int t=q.front();
            q.pop();

            for (auto &x:g[t]) {
                if (dis[x] > dis[t] + 1) {
                    dis[x] = dis[t]+1;
                    if (dis[x] < d){
                        q.push(x);
                        if (valid[x]) {
                            valid[x] = false;
                            validNodes--;
                        }
                    }
                }
            }
        }
    }

    cout<<ans<<"\n";
}

컴파일 시 표준 에러 (stderr) 메시지

catinatree.cpp: In function 'int main()':
catinatree.cpp:37:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |         auto [dist, node] = depth.back();
      |              ^

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