Ideone.com

fork download

copy

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N=500005;
const int INF=0x7FFFFFFF;
int n,e;
int S[N];
int Maxi[N];
int F[2][N];
struct edge{int x,y;edge *next;}g[N],*ls[N];
int max(int x,int y){return x>y?x:y;}
 
void addedge(int x,int y){
    g[++e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=&g[e];
}
 
void dp(){
    int i,Max;
    edge *t;
    for (i=n;i>=1;i--){
        F[0][i]=0;
        F[1][i]=1;
        Max=-INF;
        for (t=ls[i];t;t=t->next){
            F[0][i]+=F[0][t->y];
            F[1][i]+=F[0][t->y];
            if (-F[0][t->y]+F[1][t->y]>Max){
                Max=-F[0][t->y]+F[1][t->y];
                Maxi[i]=t->y;
            }
        }
        if (Max>0) F[0][i]+=Max;
              else Maxi[i]=0;
    }
}
 
void output(){
    int i,cnt;
    S[1]=0;
    for (i=1;i<=n;i++)
      for (edge *t=ls[i];t;t=t->next)
        if (!S[i] && t->y==Maxi[i])
          S[t->y]=1;
        else
          S[t->y]=0;
    cnt=0;
    for (i=1;i<=n;i++)
      cnt+=S[i];
    cout << (long long)(cnt)*1000 << "\n";
    bool first=true;
    for (i=1;i<=n;i++)
      if (S[i]){
        if (!first) printf(" ");
        printf("%d",i);
        first=false;
      }
    puts("");
}
 
int main(){
    int Tc;
    scanf("%d",&Tc);
    while (Tc--){
        scanf("%d",&n);
        e=0; memset(ls,0,sizeof(ls));
        for (int fa,i=2;i<=n;i++){
            scanf("%d",&fa);
            addedge(fa,i);
        }
        dp();
        output();
        if (Tc) puts("");
    }
}

I2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGNzdHJpbmc+CiNpbmNsdWRlIDxpb3N0cmVhbT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKY29uc3QgaW50IE49NTAwMDA1Owpjb25zdCBpbnQgSU5GPTB4N0ZGRkZGRkY7CmludCBuLGU7CmludCBTW05dOwppbnQgTWF4aVtOXTsKaW50IEZbMl1bTl07CnN0cnVjdCBlZGdle2ludCB4LHk7ZWRnZSAqbmV4dDt9Z1tOXSwqbHNbTl07CmludCBtYXgoaW50IHgsaW50IHkpe3JldHVybiB4Pnk/eDp5O30KCnZvaWQgYWRkZWRnZShpbnQgeCxpbnQgeSl7CiAgICBnWysrZV0ueD14OyBnW2VdLnk9eTsgZ1tlXS5uZXh0PWxzW3hdOyBsc1t4XT0mZ1tlXTsKfQoKdm9pZCBkcCgpewogICAgaW50IGksTWF4OwogICAgZWRnZSAqdDsKICAgIGZvciAoaT1uO2k+PTE7aS0tKXsKICAgICAgICBGWzBdW2ldPTA7CiAgICAgICAgRlsxXVtpXT0xOwogICAgICAgIE1heD0tSU5GOwogICAgICAgIGZvciAodD1sc1tpXTt0O3Q9dC0+bmV4dCl7CiAgICAgICAgICAgIEZbMF1baV0rPUZbMF1bdC0+eV07CiAgICAgICAgICAgIEZbMV1baV0rPUZbMF1bdC0+eV07CiAgICAgICAgICAgIGlmICgtRlswXVt0LT55XStGWzFdW3QtPnldPk1heCl7CiAgICAgICAgICAgICAgICBNYXg9LUZbMF1bdC0+eV0rRlsxXVt0LT55XTsKICAgICAgICAgICAgICAgIE1heGlbaV09dC0+eTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBpZiAoTWF4PjApIEZbMF1baV0rPU1heDsKICAgICAgICAgICAgICBlbHNlIE1heGlbaV09MDsKICAgIH0KfQoKdm9pZCBvdXRwdXQoKXsKICAgIGludCBpLGNudDsKICAgIFNbMV09MDsKICAgIGZvciAoaT0xO2k8PW47aSsrKQogICAgICBmb3IgKGVkZ2UgKnQ9bHNbaV07dDt0PXQtPm5leHQpCiAgICAgICAgaWYgKCFTW2ldICYmIHQtPnk9PU1heGlbaV0pCiAgICAgICAgICBTW3QtPnldPTE7CiAgICAgICAgZWxzZQogICAgICAgICAgU1t0LT55XT0wOwogICAgY250PTA7CiAgICBmb3IgKGk9MTtpPD1uO2krKykKICAgICAgY250Kz1TW2ldOwogICAgY291dCA8PCAobG9uZyBsb25nKShjbnQpKjEwMDAgPDwgIlxuIjsKICAgIGJvb2wgZmlyc3Q9dHJ1ZTsKICAgIGZvciAoaT0xO2k8PW47aSsrKQogICAgICBpZiAoU1tpXSl7CiAgICAgICAgaWYgKCFmaXJzdCkgcHJpbnRmKCIgIik7CiAgICAgICAgcHJpbnRmKCIlZCIsaSk7CiAgICAgICAgZmlyc3Q9ZmFsc2U7CiAgICAgIH0KICAgIHB1dHMoIiIpOwp9CgppbnQgbWFpbigpewogICAgaW50IFRjOwogICAgc2NhbmYoIiVkIiwmVGMpOwogICAgd2hpbGUgKFRjLS0pewogICAgICAgIHNjYW5mKCIlZCIsJm4pOwogICAgICAgIGU9MDsgbWVtc2V0KGxzLDAsc2l6ZW9mKGxzKSk7CiAgICAgICAgZm9yIChpbnQgZmEsaT0yO2k8PW47aSsrKXsKICAgICAgICAgICAgc2NhbmYoIiVkIiwmZmEpOwogICAgICAgICAgICBhZGRlZGdlKGZhLGkpOwogICAgICAgIH0KICAgICAgICBkcCgpOwogICAgICAgIG91dHB1dCgpOwogICAgICAgIGlmIChUYykgcHV0cygiIik7CiAgICB9Cn0=

Time limit exceeded #stdin compilation error #stdout -1s 18352KB

stdin

copy

Standard input is empty

compilation info

prog.cpp: In function ‘int main()’:
prog.cpp:63: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp:65: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp:68: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result

stdout

copy

https://ideone.com/LTwye

language:

C++ (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language