Submission #789955

#	Time	Username	Problem	Language	Result	Execution time	Memory
789955		1075508020060209tc	Cat in a tree (BOI17_catinatree)	C++14	51 / 100	1082 ms	15392 KiB

catinatree

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
int n;int D;
vector<int>e[200005];
int dph[200005];
int tak[200005];
void dfs(int nw,int pa){
dph[nw]=dph[pa]+1;
for(int i=0;i<e[nw].size();i++){
    int v=e[nw][i];
    if(v==pa){continue;}
    dfs(v,nw);
}
}
int dis[200005];
void bfs(vector<int>st){
queue<int>q;
for(int i=1;i<=n;i++){
    dis[i]=1e9;
}
for(int i=0;i<st.size();i++){
    q.push(st[i]);
    dis[st[i]]=0;
}
while(q.size()){
    int nw=q.front();
    q.pop();
    for(int i=0;i<e[nw].size();i++){
        int v=e[nw][i];
        if(dis[v]<=n){continue;}
        dis[v]=dis[nw]+1;
        q.push(v);
    }
}
}

signed main()
{
    cin>>n>>D;
    for(int i=2;i<=n;i++){
        int v;
        cin>>v;
        v++;
        e[v].push_back(i);
        e[i].push_back(v);
    }
    dfs(1,0);
    vector<pair<int,int>>seq;
    for(int i=1;i<=n;i++){
        seq.push_back({dph[i],i});
    }
    sort(seq.begin(),seq.end());
    reverse(seq.begin(),seq.end());
    vector<int>ans;
    ans.push_back(seq[0].second);
    for(int i=1;i<seq.size();i++){
        bfs(ans);
        int nw=seq[i].second;
        if(dis[nw]<D){continue;}else{
            ans.push_back(nw);
        }
    }
    cout<<ans.size();

}

Compilation message (stderr)

catinatree.cpp: In function 'void dfs(int, int)':
catinatree.cpp:11:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
catinatree.cpp: In function 'void bfs(std::vector<int>)':
catinatree.cpp:23:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 | for(int i=0;i<st.size();i++){
      |             ~^~~~~~~~~~
catinatree.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
catinatree.cpp: In function 'int main()':
catinatree.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i=1;i<seq.size();i++){
      |                 ~^~~~~~~~~~~

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