QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#879358 | #9696. Analysis | ucup-team139# | WA | 1ms | 3712kb | C++23 | 3.9kb | 2025-02-02 00:01:22 | 2025-02-02 00:01:22 |
Judging History
This is the latest submission verdict.
- [2025-02-06 00:45:32]
- hack成功,自动添加数据
- (/hack/1517)
- [2025-02-02 00:01:22]
- Submitted
answer
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
#include <climits>
#include <iomanip>
using namespace std;
void solve([[maybe_unused]] int t)
{
long long n, A, B;
cin >> n >> A >> B;
vector grafo(n, vector<int>());
for (int i = 0; i < n - 1; i++)
{
int u, v;
cin >> u >> v;
u--;
v--;
grafo[u].push_back(v);
grafo[v].push_back(u);
}
const long long INF = 1e15;
vector dp(n, vector(3, -1ll));
auto f = [&](auto &f, int v, int mode, int last) -> long long
{
if (dp[v][mode] != -1)
return dp[v][mode];
long long res = 0;
if (mode == 1)
{
vector<long long> tmp;
for (auto i : grafo[v])
{
if (i != last)
{
res += A + f(f, i, 0, v);
tmp.push_back(f(f, i, 1, v) - A - f(f, i, 0, v));
}
}
sort(tmp.begin(), tmp.end());
if (tmp.size() > 0)
{
res += tmp[0];
tmp.erase(tmp.begin());
}
for (int i = 0; i < tmp.size(); i += 2)
{
if (tmp[i] + (i + 1 < tmp.size() ? tmp[i + 1] : 0) + B < 0)
{
res += tmp[i] + (i + 1 < tmp.size() ? tmp[i + 1] : 0) + B;
}
else
{
break;
}
}
}
else if (mode == 0)
{
vector<long long> tmp;
for (auto i : grafo[v])
{
if (i != last)
{
res += A + f(f, i, 0, v);
tmp.push_back(f(f, i, 1, v) - A - f(f, i, 0, v));
}
}
sort(tmp.begin(), tmp.end());
if (tmp.size() == 0)
return 0;
for (int i = 0; i < tmp.size(); i += 2)
{
if (tmp[i] + (i + 1 < tmp.size() ? tmp[i + 1] : 0) + B < 0)
{
res += tmp[i] + (i + 1 < tmp.size() ? tmp[i + 1] : 0) + B;
}
else
{
break;
}
}
}
else
{
vector<long long> tmp;
for (auto i : grafo[v])
{
if (i != last)
{
res += A + f(f, i, 0, v);
tmp.push_back(f(f, i, 1, v) - A - f(f, i, 0, v));
}
}
sort(tmp.begin(), tmp.end());
if (tmp.size() == 0)
res = 0;
else
{
if (tmp.size() > 0)
{
res += tmp[0];
tmp.erase(tmp.begin());
}
if (tmp.size() > 0)
{
res += tmp[0];
tmp.erase(tmp.begin());
}
for (int i = 0; i < tmp.size(); i += 2)
{
if (tmp[i] + (i + 1 < tmp.size() ? tmp[i + 1] : 0) + B < 0)
{
res += tmp[i] + (i + 1 < tmp.size() ? tmp[i + 1] : 0) + B;
}
else
{
break;
}
}
}
tmp.clear();
long long res2 = 0, mini = INF;
for (auto i : grafo[v])
{
if (i != last)
{
res2 += A + f(f, i, 0, v);
mini = min(mini, f(f, i, 2, v) - A - f(f, i, 0, v));
}
}
res = min(res, res2 + mini);
}
// cout << v << " " << mode << " " << res << "\n";
return dp[v][mode] = res;
};
cout << f(f, 0, 2, -1) << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n = 1;
// cin >> n;
for (int i = 1; i <= n; i++)
solve(i);
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3712kb
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: 3712kb
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: 1ms
memory: 3712kb
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: 3712kb
input:
10 165074331 854297934 6 2 2 7 9 8 2 9 9 10 6 3 6 4 5 6 6 1
output:
660297324
result:
wrong answer 1st numbers differ - expected: '825371655', found: '660297324'