Submission #317133

#	Time	Username	Problem	Language	Result	Execution time	Memory
317133		daniel920712	Balanced Tree (info1cup18_balancedtree)	C++14	23 / 100	4057 ms	12792 KiB

balancedtree

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

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 root;
vector < pair < int , int > > xx,yy;
vector < int > vis;
int xxx[100005];
int yyy[100005];
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)
{
    vis.push_back(here);
    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];
    xxx[here]=2e9;
    yyy[here]=2e9;
    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,int fr)
{
    if(what[here]==0) xxx[fr]=min(xxx[fr],deg);
    if(what[here]==1) yyy[fr]=min(yyy[fr],deg);
    for(auto i:Next[here])
    {
        if(!have[i]&&i!=fa)
        {
            if(fa==-1) DFS4(i,here,deg+1,i);
            else DFS4(i,here,deg+1,fr);
        }
    }
}
void DFS5(int here,int fa,int deg,int fr)
{
    if(what[here]==0)
    {
        if(xx[0].second==fr) con[here]=min(con[here],deg+xx[1].first);
        else con[here]=min(con[here],deg+xx[0].first);
    }
    if(what[here]==1)
    {
        if(yy[0].second==fr) con[here]=min(con[here],deg+yy[1].first);
        else con[here]=min(con[here],deg+yy[0].first);
    }
    for(auto i:Next[here])
    {
        if(!have[i]&&i!=fa)
        {
            if(fa==-1) DFS5(i,here,deg+1,i);
            else DFS5(i,here,deg+1,fr);

        }
    }
}

void F2(int here)
{
    vis.clear();
    DFS2(here,-1);
    nn=sz[here];
    DFS3(here,-1);
    xxx[0]=2e9;
    yyy[0]=2e9;
    DFS4(root,-1,0,0);
    xx.clear();
    yy.clear();
    for(auto i:vis)
    {
        xx.push_back(make_pair(xxx[i],i));
        yy.push_back(make_pair(yyy[i],i));
    }
    xx.push_back(make_pair(xxx[0],0));
    yy.push_back(make_pair(yyy[0],0));
    sort(xx.begin(),xx.end());
    sort(yy.begin(),yy.end());
    if(vis.size()==1)
    {
        have[root]=1;
        return;
    }
    DFS5(root,-1,0,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:156:11: warning: unused variable 'M' [-Wunused-variable]
  156 |     int T,M,i,x=0,y=0,ok;
      |           ^
balancedtree.cpp:157:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  157 |     scanf("%d",&T);
      |     ~~~~~^~~~~~~~~
balancedtree.cpp:162:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  162 |         scanf("%d",&N);
      |         ~~~~~^~~~~~~~~
balancedtree.cpp:166:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  166 |             scanf("%d %d",&x,&y);
      |             ~~~~~^~~~~~~~~~~~~~~
balancedtree.cpp:172:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  172 |             scanf("%d",&what[i]);
      |             ~~~~~^~~~~~~~~~~~~~~

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