QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#523635 | #5041. Fire | Andyqian7 | TL | 226ms | 14732kb | C++20 | 3.4kb | 2024-08-18 15:28:14 | 2024-08-18 15:28:15 |
Judging History
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...