oj.uz

Submission #317082

# Submission time Handle Problem Language Result Execution time Memory
317082 2020-10-29T02:46:51 Z daniel920712 Balanced Tree (info1cup18_balancedtree) C++14
0 / 100
 4000 ms 524292 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[i]==-1)
        {
            what[i]=1;
            F(here+1);
            what[i]=0;
            F(here+1);
            what[i]=-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++)
        {
            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:62:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |             scanf("%d %d",&x,&y);
      |             ~~~~~^~~~~~~~~~~~~~~
balancedtree.cpp:66:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |         for(i=1;i<=N;i++) scanf("%d",&what[i]);
      |                           ~~~~~^~~~~~~~~~~~~~~
balancedtree.cpp: In function 'void F(int)':
balancedtree.cpp:41:18: warning: 'i' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |         if(what[i]==-1)
      |            ~~~~~~^

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 331 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 328 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 554 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Execution timed out 4046 ms 4864 KB Time limit exceeded
3 Runtime error 3273 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 385 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Execution timed out 4042 ms 12920 KB Time limit exceeded
3 Execution timed out 4030 ms 6912 KB Time limit exceeded

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4043 ms 3584 KB Time limit exceeded
2 Runtime error 400 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 492 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 333 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 338 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 941 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 357 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 331 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 350 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 331 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 328 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 554 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Execution timed out 4046 ms 4864 KB Time limit exceeded
5 Runtime error 3273 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 385 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Execution timed out 4042 ms 12920 KB Time limit exceeded
8 Execution timed out 4030 ms 6912 KB Time limit exceeded
9 Execution timed out 4043 ms 3584 KB Time limit exceeded
10 Runtime error 400 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 492 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 333 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 338 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 941 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 357 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 331 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 350 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 3151 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Execution timed out 4049 ms 6392 KB Time limit exceeded
20 Runtime error 329 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 55 ms 12152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 409 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)