QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#879602 | #9696. Analysis | ucup-team3695 | WA | 0ms | 12000kb | C++20 | 1.9kb | 2025-02-02 07:24:38 | 2025-02-02 07:24:38 |
Judging History
This is the latest submission verdict.
- [2025-02-06 00:45:32]
- hack成功,自动添加数据
- (/hack/1517)
- [2025-02-02 07:24:38]
- Submitted
answer
#include <bits/extc++.h>
using namespace std;
namespace rg = ranges;
constexpr int N = 1000000;
alignas(64) int I[N + 1], G[2 * N - 2], S[N - 1];
alignas(64) pair<int, int> E[N - 1];
alignas(64) pair<long long, long long> F[N];
int main()
{
cin.tie(0)->sync_with_stdio(0);
int n;
long long A, B;
cin >> n >> A >> B;
for (int i = 0; i < n - 1; i++)
{
auto &[u, v] = E[i];
cin >> u >> v;
u--;
v--;
I[u]++;
I[v]++;
}
if (n <= 2)
{
cout << "0";
return 0;
}
int r = 0;
while (I[r] == 1)
r++;
for (int i = 0; i < n; i++)
I[i + 1] += I[i];
for (int i = 0; i < n - 1; i++)
{
auto [u, v] = E[i];
G[--I[u]] = v;
G[--I[v]] = u;
}
constexpr auto diff = [](int i)
{
return F[i].first - F[i].second;
};
constexpr auto rpar = [](int u, int v)
{
for (int i = I[v]; i < I[v + 1] - 1; i++)
if (G[i] == u)
{
G[i] = G[I[v + 1] - 1];
break;
}
};
int ss = 0;
for (int i = I[r]; i < I[r + 1]; i++)
{
int v = G[i];
S[ss++] = v;
rpar(r, v);
}
while (ss)
{
int v = S[--ss];
if (v >= 0)
{
S[ss++] = v | INT_MIN;
for (int i = I[v]; i < I[v + 1] - 1; i++)
{
int w = G[i];
S[ss++] = w;
rpar(v, w);
}
}
else
{
v &= INT_MAX;
rg::sort(G + I[v], G + I[v + 1] - 1, {}, diff);
long long sum = 0;
for (int i = I[v]; i < I[v + 1] - 1; i++)
sum += F[G[i]].second;
F[v] = {sum, sum};
for (int i = I[v]; i < I[v + 1] - 1; i++)
{
int k = i - I[v] + 1;
sum += diff(G[i]);
F[v].first = min(F[v].first, sum + k / 2 * B);
F[v].second = min(F[v].second, sum + (k + 1) / 2 * B);
}
F[v].second += min(A, B);
}
}
long long sum = 0;
for (int i = I[r]; i < I[r + 1]; i++)
sum += F[G[i]].second;
long long res = sum;
for (int i = I[r]; i < I[r + 1]; i++)
{
sum += diff(G[i]);
res = min(res, sum + (i - I[r]) / 2 * B);
}
cout << res;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 11780kb
input:
5 100 1000 1 2 2 3 3 4 4 5
output:
0
result:
ok 1 number(s): "0"
Test #2:
score: 0
Accepted
time: 0ms
memory: 11872kb
input:
5 100 200 1 2 1 3 2 4 2 5
output:
100
result:
ok 1 number(s): "100"
Test #3:
score: 0
Accepted
time: 0ms
memory: 11992kb
input:
10 133494816 109943166 10 8 5 3 1 2 8 9 8 5 2 4 8 7 8 6 10 1
output:
219886332
result:
ok 1 number(s): "219886332"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 12000kb
input:
10 165074331 854297934 6 2 2 7 9 8 2 9 9 10 6 3 6 4 5 6 6 1
output:
990445986
result:
wrong answer 1st numbers differ - expected: '825371655', found: '990445986'