Submission #317084

#	Time	Username	Problem	Language	Result	Execution time	Memory
317084		daniel920712	Balanced Tree (info1cup18_balancedtree)	C++14	10 / 100	4104 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 ans=0,now,N;
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 main()
{
    int T,M,i,x,y;
    scanf("%d",&T);
    while(T--)
    {
        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]);
        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");
        }
    }
    return 0;
}

Compilation message (stderr)

balancedtree.cpp: In function 'int main()':
balancedtree.cpp:54:11: warning: unused variable 'M' [-Wunused-variable]
   54 |     int T,M,i,x,y;
      |           ^
balancedtree.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |     scanf("%d",&T);
      |     ~~~~~^~~~~~~~~
balancedtree.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |         scanf("%d",&N);
      |         ~~~~~^~~~~~~~~
balancedtree.cpp:63:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |             scanf("%d %d",&x,&y);
      |             ~~~~~^~~~~~~~~~~~~~~
balancedtree.cpp:67:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |         for(i=1;i<=N;i++) scanf("%d",&what[i]);
      |                           ~~~~~^~~~~~~~~~~~~~~

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