QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#523618#5041. FireAndyqian7RE 0ms3824kbC++203.4kb2024-08-18 15:12:152024-08-18 15:12:15

Judging History

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

  • [2024-08-18 15:12:15]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3824kb
  • [2024-08-18 15:12:15]
  • 提交

answer

#include <bits/stdc++.h>
#define lowbit(x) x & -x
#define rep(i, s, e) for (int i = s; i <= e; i++)
using namespace std;
const int MAX = 1e2 + 10;
int n, m, k, a[MAX], f[MAX], g[MAX], sz[MAX];
vector<int> nei[MAX], sons[MAX];
void build(int s)
{
    sz[s] = 1;
    for (int n : nei[s])
    {
        if (sz[n])
            continue;
        build(n);
        sz[s] += sz[n];
        sons[s].push_back(n);
    }
}
struct node
{
    int dp, sz;
    friend bool operator<(const node &x, const node &y)
    {
        return x.sz > y.sz;
    }
};
void dfs(int s)
{
    for (int son : sons[s])
    {
        dfs(son);
    }
    int l = -1, r = a[s] + k - 2 * (sz[s] - 1) - 2;
    while (l < r)
    {
        int mid = (l + r + 1) / 2;
        vector<node> v;
        m = sons[s].size();
        for (int son : sons[s])
        {
            v.push_back({f[son], sz[son]});
        }
        sort(v.begin(), v.end(), [](const node &x, const node &y)
             { return x.dp + 2 * x.sz > y.dp + 2 * y.sz; });
        priority_queue<node> Q;
        int tmp = mid + 2 * (sz[s] - 1) + 1, pos = 0, sum = 0; // sum of 2*sz not inclusive
        bool sign = 1;
        rep(i, 1, m)
        {
            for (; pos < m && sum + v[pos].dp + 2 * v[pos].sz >= tmp; pos++)
            {
                Q.push(v[pos]);
            }
            if (Q.empty())
            {
                sign = 0;
                break;
            }
            auto [dp, sz] = Q.top();
            Q.pop();
            sum += 2 * sz;
        }
        if (sign)
            l = mid;
        else
            r = mid - 1;
    }
    f[s] = l;
    if (sons[s].empty())
    {
        g[s] = a[s];
        return;
    }
    l = -1, r = a[s] + k;
    while (l < r)
    {
        int mid = (l + r + 1) / 2;
        int ma = -1e9, mapo = -1;
        for (int son : sons[s])
        {
            if (g[son] + 2 * sz[son] >= mid + 2 * sz[s] - 1 && sz[son] > ma)
            {
                mapo = son;
                ma = sz[son];
            }
        }
        bool sign = 1;
        if (mapo == -1)
            sign = 0;
        if (a[s] + k - mid - 2 * (sz[s] - ma) < 0)
            sign = 0;
        vector<node> v;
        for (int son : sons[s])
        {
            if (son != mapo)
            {
                v.push_back({f[son], sz[son]});
            }
        }
        sort(v.begin(), v.end(), [](const node &x, const node &y)
             { return x.dp + 2 * x.sz > y.dp + 2 * y.sz; });
        priority_queue<node> Q;
        m = v.size();
        int tmp = mid + 2 * (sz[s] - 1 - ma) + 1, pos = 0, sum = 0; // sum of 2*sz not inclusive
        rep(i, 1, m)
        {
            for (; pos < m && sum + v[pos].dp + 2 * v[pos].sz >= tmp; pos++)
            {
                Q.push(v[pos]);
            }
            if (Q.empty())
            {
                sign = 0;
                break;
            }
            auto [dp, sz] = Q.top();
            Q.pop();
            sum += 2 * sz;
        }
        if (sign)
            l = mid;
        else
            r = mid - 1;
    }
    g[s] = l;
}
int main()
{
    cin >> n >> k;
    rep(i, 1, n - 1)
    {
        int x, y;
        cin >> x >> y;
        nei[x].push_back(y), nei[y].push_back(x);
    }
    build(1);
    rep(i, 1, n) cin >> a[i];
    dfs(1);
    cout << g[1];
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3824kb

input:

3 1
1 2
1 3
4 3 5

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

3 1
1 2
1 3
2 10 10

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

2 0
1 2
10 10

output:

8

result:

ok 1 number(s): "8"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

3 0
1 2
3 1
10 8 10

output:

5

result:

ok 1 number(s): "5"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

10 0
9 7
2 7
2 1
4 7
9 6
7 3
8 10
9 10
8 5
29 24 27 22 20 25 23 29 20 20

output:

8

result:

ok 1 number(s): "8"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

100 0
82 86
79 53
86 24
64 74
3 26
65 91
47 35
73 90
8 75
59 27
78 19
76 20
34 7
82 31
11 20
4 85
52 16
46 51
93 52
87 20
82 6
64 92
52 2
54 62
60 63
69 95
24 90
54 25
9 72
2 20
27 82
29 25
43 85
57 92
36 77
22 81
14 84
69 49
20 47
52 98
97 88
23 45
1 87
56 45
31 36
85 31
44 83
33 53
10 78
37 40
13 ...

output:

52

result:

ok 1 number(s): "52"

Test #7:

score: -100
Runtime Error

input:

1000 0
781 478
708 997
164 3
242 868
210 828
349 149
376 785
332 690
182 514
552 322
461 542
124 559
402 695
99 989
590 295
540 310
115 624
903 158
915 162
832 238
382 796
860 198
620 262
815 436
494 546
162 173
853 376
731 770
444 702
337 722
995 306
839 489
464 843
761 309
562 88
27 852
192 530
19...

output:


result: