QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#523619#5041. FireAndyqian7WA 262ms14940kbC++203.4kb2024-08-18 15:12:322024-08-18 15:12:32

Judging History

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

  • [2024-08-18 15:12:32]
  • 评测
  • 测评结果:WA
  • 用时:262ms
  • 内存:14940kb
  • [2024-08-18 15:12:32]
  • 提交

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 = 1e5 + 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: 5696kb

input:

3 1
1 2
1 3
4 3 5

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3652kb

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: 3816kb

input:

2 0
1 2
10 10

output:

8

result:

ok 1 number(s): "8"

Test #4:

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

input:

3 0
1 2
3 1
10 8 10

output:

5

result:

ok 1 number(s): "5"

Test #5:

score: 0
Accepted
time: 1ms
memory: 5728kb

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: 1ms
memory: 3652kb

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: 0
Accepted
time: 2ms
memory: 5784kb

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:

208

result:

ok 1 number(s): "208"

Test #8:

score: 0
Accepted
time: 17ms
memory: 6700kb

input:

10000 0
8532 1309
7924 7641
3850 2342
5333 6578
4919 6615
2937 1134
7202 3833
3118 5150
3032 423
5684 647
2038 5418
7810 4255
6912 8228
6136 7472
1889 4121
9348 7211
8439 4505
9915 7800
5500 8587
4261 8149
9496 243
8502 4248
4838 3073
994 3446
5177 3384
2216 9983
3930 2243
6638 5154
1991 3731
4216 1...

output:

800

result:

ok 1 number(s): "800"

Test #9:

score: 0
Accepted
time: 186ms
memory: 14940kb

input:

100000 0
7792 26010
85804 1078
82899 25724
47158 81804
60588 36038
7704 64781
50035 14650
92695 7665
27387 75724
19543 53096
50134 64624
77873 18941
18330 34916
31993 22809
40207 54229
55324 55105
16997 96779
63858 97958
40532 31166
13028 2225
92083 90328
39005 67586
66623 36043
84284 79134
84722 35...

output:

3231

result:

ok 1 number(s): "3231"

Test #10:

score: 0
Accepted
time: 262ms
memory: 14672kb

input:

100000 0
84175 9629
86499 8316
10499 32549
6203 8049
73531 21696
59782 18131
48682 49498
84503 78323
35878 37155
72866 95140
70292 39353
65243 8130
33496 52738
74044 44275
15789 35130
55929 34691
71587 2066
14877 70981
76619 50488
89347 78338
57879 13747
47955 45641
98403 44863
90240 41682
67754 110...

output:

-1

result:

ok 1 number(s): "-1"

Test #11:

score: 0
Accepted
time: 1ms
memory: 5924kb

input:

10 0
1 7
5 7
6 9
8 2
3 1
9 10
9 2
8 4
5 9
1 7 5 4 10 8 1 6 0 4

output:

-1

result:

ok 1 number(s): "-1"

Test #12:

score: 0
Accepted
time: 8ms
memory: 3916kb

input:

2962 0
1802 1648
2780 474
20 2923
1902 2515
2650 1040
31 74
1753 392
1635 2719
2900 1286
1158 1227
1881 2316
1983 290
881 724
2904 1365
574 118
167 1726
2029 1208
2731 2451
113 2012
1763 2666
1489 145
1165 2201
2691 2141
126 2903
194 1476
2345 1025
1809 1964
1406 2362
305 1192
2007 1415
2957 1122
22...

output:

38596

result:

ok 1 number(s): "38596"

Test #13:

score: 0
Accepted
time: 149ms
memory: 10020kb

input:

58346 0
32606 33231
10774 14178
56179 20149
4402 53574
30314 6332
47840 23093
49961 30471
1558 7974
981 26443
44800 53897
7501 56273
24880 56072
21534 32688
56597 49273
29017 29780
4351 49319
29361 20740
2603 15303
57792 6137
8823 41985
25290 18398
57356 23079
15412 16730
27348 1294
28703 15186
1476...

output:

199014

result:

ok 1 number(s): "199014"

Test #14:

score: 0
Accepted
time: 29ms
memory: 6956kb

input:

11327 0
6972 5303
4106 6016
10927 1269
10358 846
8138 7882
5083 2862
1623 4163
10328 10962
6629 2486
6706 5247
155 1179
6717 9319
918 11081
7491 10594
3042 7403
1275 100
5567 10436
8364 11318
8532 4071
3070 9038
9635 4091
233 9658
1127 6631
37 5223
4314 1203
8162 8875
9962 10547
7578 9494
10083 9960...

output:

130321

result:

ok 1 number(s): "130321"

Test #15:

score: -100
Wrong Answer
time: 1ms
memory: 5628kb

input:

2 805038099
2 1
5 9

output:

8

result:

wrong answer 1st numbers differ - expected: '5', found: '8'