Submission #317124

#	Time	Username	Problem	Language	Result	Execution time	Memory
317124		daniel920712	Balanced Tree (info1cup18_balancedtree)	C++14	0 / 100	4053 ms	12792 KiB

balancedtree

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;
vector < int > Next[100005];
int what[100005];
int Ans[1000005];
int con[1000005];
int sz[1000005];
int ans=0,now,N,nn;
bool have[1000005];
int xx,yy,root;
void DFS(int st,int here,int fa,int deg)
{
    if(st!=here) if(what[here]==what[st]) now=min(now,deg);
    for(auto i:Next[here])
    {
        if(i!=fa)
        {
            DFS(st,i,here,deg+1);
        }
    }

}
void F(int here)
{
    int t,i;
    if(here==N+1)
    {
        t=0;
        for(i=1;i<=N;i++)
        {
            now=2e9;
            DFS(i,i,-1,0);
            t=max(t,now);
        }
        ans=min(ans,t);
        if(t==ans) for(i=1;i<=N;i++) Ans[i]=what[i];

    }
    else
    {
        if(what[here]==-1)
        {
            what[here]=1;
            F(here+1);
            what[here]=0;
            F(here+1);
            what[here]=-1;
        }
        else F(here+1);
    }
}
int DFS2(int here,int fa)
{
    sz[here]=1;
    for(auto i:Next[here])
    {
        if(!have[i]&&i!=fa)
        {
            sz[here]+=DFS2(i,here);
        }
    }
    return sz[here];
}
void DFS3(int here,int fa)
{
    int t=nn-sz[here];
    for(auto i:Next[here])
    {
        if(!have[i]&&i!=fa)
        {
            DFS3(i,here);
            t=max(t,sz[i]);
        }
    }
    if(t<=nn/2) root=here;
}
void DFS4(int here,int fa,int deg)
{
    if(what[here]==0) xx=min(xx,deg);
    if(what[here]==1) yy=min(yy,deg);
    for(auto i:Next[here])
    {
        if(!have[i]&&i!=fa)
        {
            DFS4(i,here,deg+1);
        }
    }
}
void DFS5(int here,int fa,int deg)
{
    if(what[here]==0) con[here]=min(con[here],deg+xx);
    if(what[here]==1) con[here]=min(con[here],deg+yy);
    for(auto i:Next[here])
    {
        if(!have[i]&&i!=fa)
        {
            DFS5(i,here,deg+1);

        }
    }
}

void F2(int here)
{
    DFS2(here,-1);
    nn=sz[here];
    DFS3(here,-1);
    xx=2e9;
    yy=2e9;
    DFS4(root,-1,0);
    DFS5(root,-1,0);
    have[root]=1;
    for(auto i:Next[root]) if(!have[i]) F2(i);
}
int main()
{
    int T,M,i,x=0,y=0,ok;
    scanf("%d",&T);
    while(T--)
    {
        ok=0;
        ans=2e9;
        scanf("%d",&N);
        for(i=1;i<=N;i++) Next[i].clear();
        for(i=1;i<N;i++)
        {
            scanf("%d %d",&x,&y);
            Next[x].push_back(y);
            Next[y].push_back(x);
        }
        for(i=1;i<=N;i++)
        {
            scanf("%d",&what[i]);
            if(what[i]==-1) ok=1;
        }
        if(ok)
        {
            F(1);
            if(ans==2000000000) printf("-1\n");
            else
            {
                printf("%d\n",ans);
                for(i=1;i<=N;i++) printf("%d ",Ans[i]);
                printf("\n");
            }
        }
        else
        {
            x=0;
            y=0;
            for(i=1;i<=N;i++)
            {
                have[i]=0;
                con[i]=2e9;
                if(what[i]==1) x++;
                else y++;
            }
            if(x==1||y==1) printf("-1\n");
            else
            {
                ans=0;
                F2(1);
                for(i=1;i<=N;i++) ans=max(ans,con[i]);
                printf("%d\n",ans);
                for(i=1;i<=N;i++) printf("%d ",what[i]);
                printf("\n");


            }
        }

    }
    return 0;
}

Compilation message (stderr)

balancedtree.cpp: In function 'int main()':
balancedtree.cpp:121:11: warning: unused variable 'M' [-Wunused-variable]
  121 |     int T,M,i,x=0,y=0,ok;
      |           ^
balancedtree.cpp:122:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  122 |     scanf("%d",&T);
      |     ~~~~~^~~~~~~~~
balancedtree.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  127 |         scanf("%d",&N);
      |         ~~~~~^~~~~~~~~
balancedtree.cpp:131:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  131 |             scanf("%d %d",&x,&y);
      |             ~~~~~^~~~~~~~~~~~~~~
balancedtree.cpp:137:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  137 |             scanf("%d",&what[i]);
      |             ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 26
• Subtask 4: 0 / 45
• Subtask 5: 0 / 6