QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#781773	#9806. Growing Tree	ucup-team902	TL	3718ms	4064kb	C++17	2.4kb	2024-11-25 17:27:21	2024-11-25 17:27:21

Judging History

你现在查看的是最新测评结果

[2024-11-25 17:27:21]
评测

测评结果：TL
用时：3718ms
内存：4064kb

查看

[2024-11-25 17:27:21]
提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 11;
int n;
int a[N + 5];
int cnt[N + 5];
int lca(int x, int y)
{
    int k = (int)log2(x ^ y);
    return x >> (k + 1);
}
int del[N + 5];
int cc[15], ans;
void dfs(int s)
{
    if (s > n)
        return;
    int u = -1;
    for (int i = 1; i < (1 << n); i++)
        if (cnt[i])
            u = i;
    // printf("%d\n", u);
    if (u == -1)
    {
        int t = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            t += cc[i];
            if (t > n - i)
                return;
        }
        ans = min(ans, s);
        return;
    }
    int d = (int)log2(u);
    cc[d]++;
    int l = (u << 1) << (n - d - 1), r = (u << 1 | 1) << (n - d - 1);
    for (int i = l; i < r; i++)
    {
        if (!del[i])
        {
            for (int j = (1 << n); j < (1 << n + 1); j++)
                if (!del[j] && i != j && a[i] == a[j])
                    cnt[lca(i, j)]--;
        }
        del[i]++;
    }
    dfs(s + 1);
    for (int i = l; i < r; i++)
    {
        del[i]--;
        if (!del[i])
        {
            for (int j = (1 << n); j < (1 << n + 1); j++)
                if (!del[j] && i != j && a[i] == a[j])
                    cnt[lca(i, j)]++;
        }
    }
    l = r;
    r = (u + 1 << 1) << (n - d - 1);
    for (int i = l; i < r; i++)
    {
        if (!del[i])
        {
            for (int j = (1 << n); j < (1 << n + 1); j++)
                if (!del[j] && i != j && a[i] == a[j])
                    cnt[lca(i, j)]--;
        }
        del[i]++;
    }
    dfs(s + 1);
    for (int i = l; i < r; i++)
    {
        del[i]--;
        if (!del[i])
        {
            for (int j = (1 << n); j < (1 << n + 1); j++)
                if (!del[j] && i != j && a[i] == a[j])
                    cnt[lca(i, j)]++;
        }
    }
    cc[d]--;
}
void solve()
{
    scanf("%d", &n);
    a[1] = 0;
    for (int i = 2; i < (1 << n + 1); i++)
    {
        scanf("%d", &a[i]);
        a[i] += a[i >> 1];
    }
    for (int i = (1 << n); i < (1 << n + 1); i++)
        for (int j = i + 1; j < (1 << n + 1); j++)
            if (a[i] == a[j])
                cnt[lca(i, j)]++;
    ans = n + 1;
    dfs(0);
    if (ans == n + 1)
        ans = -1;
    printf("%d\n", ans);
    memset(cnt, 0, sizeof cnt);
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
        solve();
    return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3968kb

input:

3
2
1 2 4 3 2 1
2
1 2 3 3 2 1
2
1 2 3 3 1 1

output:

1
2
-1

result:

ok 3 number(s): "1 2 -1"

Test #2:

score: 0

Accepted

time: 66ms

memory: 3988kb

input:

94
5
44 65 38 61 64 94 71 53 65 10 24 36 98 74 11 4 5 46 72 34 9 24 37 32 76 29 48 88 17 14 36 4 22 6 71 53 24 61 89 79 39 57 99 61 27 85 99 46 81 75 90 25 16 13 1 87 55 81 56 78 67 2
3
83 3 74 14 45 17 22 41 62 74 25 1 56 22
7
21 73 83 99 3 91 16 53 8 10 49 29 54 81 45 10 12 68 32 9 30 11 99 85 73 ...

output:

result:

ok 94 numbers

Test #3:

score: 0

Accepted

time: 81ms

memory: 3980kb

input:

1
10
100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 10000...

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: 0

Accepted

time: 2058ms

memory: 4032kb

input:

1000
7
50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 1000 numbers

Test #5:

score: 0

Accepted

time: 152ms

memory: 3900kb

input:

1000
6
50000001 50000000 49999999 50000001 49999999 50000001 49999999 50000001 49999999 50000000 50000001 50000001 50000000 49999999 50000001 50000000 49999999 49999999 50000001 50000001 50000001 49999999 50000001 49999999 50000001 50000000 50000001 50000001 50000001 50000000 50000000 49999999 50000...

output:

-1
2
3
1
-1
-1
-1
-1
1
1
-1
-1
2
-1
0
0
0
-1
1
-1
-1
1
-1
0
1
-1
-1
2
-1
-1
-1
-1
1
-1
2
-1
-1
1
1
-1
1
0
2
-1
-1
-1
3
-1
-1
1
2
1
1
2
-1
-1
-1
3
-1
-1
-1
-1
3
-1
-1
-1
-1
1
-1
-1
-1
-1
2
0
-1
-1
-1
-1
1
1
-1
1
-1
1
-1
-1
-1
-1
-1
-1
1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
2
2
-1
-1
-1
0
-1
-1
0
3
-1
-1
-1...

result:

ok 1000 numbers

Test #6:

score: 0

Accepted

time: 98ms

memory: 3992kb

input:

1000
7
50000001 50000001 50000001 49999999 50000002 49999999 49999999 50000001 49999999 49999998 50000002 50000000 50000000 50000002 49999998 50000000 50000001 49999999 50000001 49999998 50000000 49999998 49999999 49999998 50000001 50000000 49999999 49999999 49999998 49999999 50000000 49999999 50000...

output:

-1
-1
1
2
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
2
0
0
-1
1
1
-1
1
-1
2
0
-1
-1
-1
-1
0
-1
1
4
-1
3
-1
-1
2
-1
2
2
0
-1
0
-1
-1
-1
0
-1
1
-1
-1
-1
3
2
-1
3
1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
2
1
1
-1
-1
-1
-1
0
-1
-1
0
4
-1
-1
1
-1
-1
-1
1
-1
-1
2
1
-1
-1
2
-1
1
1
-1
-1
0
-1
-1
3
-1
-1
0
-1
1
-1
-1
-1
-...

result:

ok 1000 numbers

Test #7:

score: 0

Accepted

time: 144ms

memory: 4004kb

input:

1000
1
50000002 50000004
6
49999995 49999996 50000000 49999998 49999997 49999998 50000002 49999998 50000003 49999998 49999995 50000001 49999998 50000005 49999999 50000001 49999995 49999995 49999996 50000002 49999997 50000005 49999998 49999996 49999998 50000002 50000003 49999996 50000004 49999998 500...

output:

0
-1
-1
-1
0
1
-1
0
-1
-1
-1
0
2
3
-1
-1
-1
4
-1
-1
0
-1
0
-1
-1
1
0
-1
3
2
1
0
3
0
-1
-1
0
1
0
2
-1
-1
-1
0
3
1
0
0
3
-1
-1
2
-1
-1
-1
0
1
1
1
1
1
-1
2
-1
-1
-1
2
-1
0
-1
-1
0
2
-1
0
-1
2
1
2
-1
-1
-1
1
-1
0
-1
-1
-1
-1
4
-1
-1
-1
-1
-1
-1
4
0
-1
-1
-1
-1
0
2
2
-1
0
-1
-1
0
0
1
0
-1
0
0
-1
0
0
3
-1...

result:

ok 1000 numbers

Test #8:

score: 0

Accepted

time: 160ms

memory: 3852kb

input:

1000
7
50000005 50000000 50000005 49999994 49999998 49999996 50000002 49999998 49999999 49999999 50000004 49999995 50000009 49999995 49999997 50000000 49999992 50000006 50000003 50000008 50000003 49999991 49999998 50000001 49999997 49999990 50000007 49999998 50000007 49999999 50000009 49999998 49999...

output:

result:

ok 1000 numbers

Test #9:

score: 0

Accepted

time: 1022ms

memory: 4000kb

input:

1000
7
49999988 49999986 50000013 50000001 49999982 50000000 50000010 49999984 50000019 50000011 50000001 50000012 50000016 50000009 49999984 49999985 49999989 50000000 50000015 49999981 50000002 50000013 50000001 50000019 50000009 50000007 50000014 49999999 49999997 49999997 49999998 49999996 50000...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 1000 numbers

Test #10:

score: 0

Accepted

time: 1787ms

memory: 3976kb

input:

1000
7
49999953 49999968 49999984 49999956 50000008 50000033 49999983 49999989 50000027 49999958 50000036 50000043 50000038 49999957 50000026 49999952 49999955 50000028 49999983 50000008 50000036 50000049 49999985 49999959 49999955 50000012 49999993 49999969 49999997 49999966 50000017 50000022 50000...

output:

-1
-1
-1
-1
6
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
6
-1
-1
-1
6
-1
6
5
-1
-1
-1
7
-1
6
6
-1
-1
6
6
-1
7
-1
6
-1
-1
-1
-1
6
-1
-1
-1
6
-1
-1
6
-1
-1
-1
-1
6
5
-1
-1
5
-1
-1
-1
-1
6
-1
-1
-1
-1
-1
-1
7
-1
7
-1
-1
6
-1
6
6
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
6
-1
6
5
6
-1
4
7
-1
-1
-1
-1
-1
...

result:

ok 1000 numbers

Test #11:

score: 0

Accepted

time: 1087ms

memory: 4064kb

input:

1000
7
50000069 49999968 49999970 50000014 50000066 50000093 50000078 50000045 49999984 50000042 49999980 49999981 50000100 49999934 49999964 49999984 50000023 49999950 49999929 50000057 49999965 50000095 50000059 49999910 50000014 50000006 50000060 49999991 50000014 49999946 50000072 49999919 49999...

output:

result:

ok 1000 numbers

Test #12:

score: 0

Accepted

time: 1048ms

memory: 4016kb

input:

1000
7
50000094 49999913 50000055 49999859 49999841 50000015 50000042 50000089 49999834 50000128 49999964 49999820 49999911 50000112 49999910 49999960 49999918 50000061 50000080 50000023 49999887 49999934 50000029 49999863 50000031 49999862 49999908 49999891 50000093 49999909 50000015 50000099 50000...

output:

result:

ok 1000 numbers

Test #13:

score: 0

Accepted

time: 1605ms

memory: 3940kb

input:

1000
7
49999647 50000321 50000292 49999681 50000305 49999618 50000278 49999677 49999976 49999581 49999501 50000223 50000139 49999633 49999672 50000252 50000158 49999589 49999529 50000123 50000324 49999565 49999573 49999766 49999719 49999674 50000171 49999667 50000080 50000086 49999535 50000008 50000...

output:

result:

ok 1000 numbers

Test #14:

score: 0

Accepted

time: 3718ms

memory: 4060kb

input:

1000
7
49999296 50000153 49999247 50000001 49999647 50000551 50000894 50000684 49999095 50000634 50000853 50000116 49999968 49999634 50000930 50000569 50000547 50000870 50000219 49999656 49999913 50000748 49999296 50000129 49999664 50000266 49999096 49999687 50000986 50000301 50000019 50000444 50000...

output:

result:

ok 1000 numbers

Test #15:

score: -100

Time Limit Exceeded

input:

1000
7
50001954 50001257 49999003 50000567 50000029 50001824 49999008 49998588 49998872 49998692 49999609 49999765 49998988 49998766 50001881 49999615 50001806 50001690 49998880 50001629 49999472 50000395 49999551 49998733 49999199 50001325 49998419 50000167 50001687 49999326 49998552 49999754 50001...

output: