QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#523635#5041. FireAndyqian7TL 226ms14732kbC++203.4kb2024-08-18 15:28:142024-08-18 15:28:15

Judging History

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

  • [2024-08-18 15:28:15]
  • 评测
  • 测评结果:TL
  • 用时:226ms
  • 内存:14732kb
  • [2024-08-18 15:28:14]
  • 提交

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] = min(a[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] = min(a[s], l);
}
int main()
{
    ios::sync_with_stdio(0);
    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: 1ms
memory: 5600kb

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

input:

3 1
1 2
1 3
2 10 10

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

input:

2 0
1 2
10 10

output:

8

result:

ok 1 number(s): "8"

Test #4:

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

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

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

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

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: 10ms
memory: 4720kb

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: 156ms
memory: 14732kb

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: 226ms
memory: 14704kb

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: 0ms
memory: 5544kb

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

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: 127ms
memory: 10124kb

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: 25ms
memory: 5036kb

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: 0
Accepted
time: 1ms
memory: 5608kb

input:

2 805038099
2 1
5 9

output:

5

result:

ok 1 number(s): "5"

Test #16:

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

input:

3 734875350
3 1
2 1
7 10 6

output:

5

result:

ok 1 number(s): "5"

Test #17:

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

input:

10 32745800
10 4
3 2
3 8
2 5
1 7
10 8
7 9
10 9
6 10
29 26 23 25 28 23 24 25 27 22

output:

14

result:

ok 1 number(s): "14"

Test #18:

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

input:

100 162383393
31 34
21 51
57 12
10 23
32 95
41 92
53 30
69 1
56 14
96 88
78 19
58 54
66 27
79 17
53 87
45 47
67 8
27 91
44 37
31 81
63 46
45 67
98 31
39 38
68 23
30 29
67 81
24 12
19 71
44 15
71 81
68 45
6 97
89 1
67 3
48 98
95 3
47 4
37 51
90 14
70 55
37 96
55 26
25 80
42 83
72 7
24 82
43 61
9 69
5...

output:

67

result:

ok 1 number(s): "67"

Test #19:

score: 0
Accepted
time: 3ms
memory: 5776kb

input:

1000 400949318
343 110
979 419
316 662
283 195
334 350
892 613
343 6
644 801
394 234
651 772
921 738
425 271
102 154
818 811
97 620
390 850
460 431
535 9
839 685
884 400
882 936
228 803
670 830
762 123
848 354
441 723
703 682
350 761
595 311
357 183
326 581
139 722
646 49
611 573
909 635
947 195
687...

output:

299

result:

ok 1 number(s): "299"

Test #20:

score: 0
Accepted
time: 16ms
memory: 6664kb

input:

10000 345823004
1052 7766
9530 9030
1427 4568
8079 9988
9057 3199
1478 1945
1322 2897
886 4298
6772 2872
4758 2792
9275 3241
1365 4822
234 9912
1900 7302
534 4359
3530 6115
7067 5594
1948 9727
2263 201
5548 1883
8634 5112
9156 2164
5373 2690
5283 9117
8432 7915
8402 9694
1720 5987
4135 855
8367 3454...

output:

796

result:

ok 1 number(s): "796"

Test #21:

score: 0
Accepted
time: 208ms
memory: 14716kb

input:

100000 707231131
48773 38777
48832 96886
94005 20847
38184 84385
26610 39096
18584 87622
96709 70406
6354 93077
66183 85208
54420 35056
24557 33014
51714 40562
97634 3359
19217 50246
22794 22879
85047 61794
96031 99822
85657 28479
62933 32355
74722 13899
37385 57342
16229 67758
43018 75542
29646 630...

output:

3050

result:

ok 1 number(s): "3050"

Test #22:

score: -100
Time Limit Exceeded

input:

100000 624542748
54339 88265
37391 93706
49793 31645
90363 86128
70644 12453
68826 38323
67188 43865
55385 35808
88297 39728
19961 32839
57392 76128
64718 33196
93633 84549
14791 21346
23104 57259
66650 48150
24762 78150
27546 63300
58622 82239
65024 68584
99336 76052
77041 37286
16427 41240
23444 4...

output:


result: