QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#523626 | #5041. Fire | Andyqian7 | WA | 274ms | 14772kb | C++20 | 3.4kb | 2024-08-18 15:19:03 | 2024-08-18 15:19:04 |
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] = 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 << min(a[1], g[1]);
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5896kb
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: 5684kb
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: 5924kb
input:
2 0 1 2 10 10
output:
8
result:
ok 1 number(s): "8"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5888kb
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: 3620kb
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: 5580kb
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: 5760kb
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: 16ms
memory: 4692kb
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: 191ms
memory: 14772kb
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: 274ms
memory: 14680kb
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: 5724kb
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: 5ms
memory: 5972kb
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: 150ms
memory: 10072kb
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: 30ms
memory: 6908kb
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: 5600kb
input:
2 805038099 2 1 5 9
output:
5
result:
ok 1 number(s): "5"
Test #16:
score: -100
Wrong Answer
time: 0ms
memory: 5688kb
input:
3 734875350 3 1 2 1 7 10 6
output:
7
result:
wrong answer 1st numbers differ - expected: '5', found: '7'