oj.uz

Submission #317084

# Submission time Handle Problem Language Result Execution time Memory
317084 2020-10-29T02:50:30 Z daniel920712 Balanced Tree (info1cup18_balancedtree) C++14
10 / 100
 4000 ms 12792 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2688 KB Output is correct
2 Correct 26 ms 2688 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 3320 KB Output is correct
2 Execution timed out 4104 ms 4600 KB Time limit exceeded
3 Execution timed out 4038 ms 3456 KB Time limit exceeded

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4027 ms 2816 KB Time limit exceeded
2 Execution timed out 4045 ms 12792 KB Time limit exceeded
3 Execution timed out 4024 ms 6528 KB Time limit exceeded

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4042 ms 3456 KB Time limit exceeded
2 Execution timed out 4045 ms 2936 KB Time limit exceeded
3 Execution timed out 4027 ms 2944 KB Time limit exceeded
4 Execution timed out 4032 ms 2688 KB Time limit exceeded
5 Execution timed out 4024 ms 2688 KB Time limit exceeded
6 Execution timed out 4033 ms 3320 KB Time limit exceeded
7 Execution timed out 4018 ms 2816 KB Time limit exceeded
8 Execution timed out 4021 ms 2688 KB Time limit exceeded
9 Execution timed out 4033 ms 2816 KB Time limit exceeded

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2688 KB Output is correct
2 Correct 26 ms 2688 KB Output is correct
3 Correct 156 ms 3320 KB Output is correct
4 Execution timed out 4104 ms 4600 KB Time limit exceeded
5 Execution timed out 4038 ms 3456 KB Time limit exceeded
6 Execution timed out 4027 ms 2816 KB Time limit exceeded
7 Execution timed out 4045 ms 12792 KB Time limit exceeded
8 Execution timed out 4024 ms 6528 KB Time limit exceeded
9 Execution timed out 4042 ms 3456 KB Time limit exceeded
10 Execution timed out 4045 ms 2936 KB Time limit exceeded
11 Execution timed out 4027 ms 2944 KB Time limit exceeded
12 Execution timed out 4032 ms 2688 KB Time limit exceeded
13 Execution timed out 4024 ms 2688 KB Time limit exceeded
14 Execution timed out 4033 ms 3320 KB Time limit exceeded
15 Execution timed out 4018 ms 2816 KB Time limit exceeded
16 Execution timed out 4021 ms 2688 KB Time limit exceeded
17 Execution timed out 4033 ms 2816 KB Time limit exceeded
18 Execution timed out 4073 ms 3104 KB Time limit exceeded
19 Execution timed out 4019 ms 6588 KB Time limit exceeded
20 Execution timed out 4026 ms 2688 KB Time limit exceeded
21 Runtime error 6 ms 5248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Execution timed out 4059 ms 2688 KB Time limit exceeded