QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #523618 | #5041. Fire | Andyqian7 | RE | 0ms | 3824kb | C++20 | 3.4kb | 2024-08-18 15:12:15 | 2024-08-18 15:12: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 = 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];
}
Details
Tip: Click on the bar to expand more detailed information
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...