QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#523615 | #5041. Fire | Andyqian7 | WA | 1ms | 5932kb | C++20 | 3.4kb | 2024-08-18 14:57:04 | 2024-08-18 14:57:05 |
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] = max(-1, a[s] - 1);
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 - sz[mapo]) + 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: 5688kb
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: 5932kb
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: 3596kb
input:
2 0 1 2 10 10
output:
8
result:
ok 1 number(s): "8"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5928kb
input:
3 0 1 2 3 1 10 8 10
output:
5
result:
ok 1 number(s): "5"
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 3592kb
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:
7
result:
wrong answer 1st numbers differ - expected: '8', found: '7'