QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#878361 | #9696. Analysis | ucup-team3802# | WA | 0ms | 3712kb | C++23 | 1.6kb | 2025-02-01 14:57:47 | 2025-02-01 14:57:50 |
Judging History
This is the latest submission verdict.
- [2025-02-06 00:45:32]
- hack成功,自动添加数据
- (/hack/1517)
- [2025-02-01 14:57:47]
- Submitted
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, l, r) for(ll i = l; i < r; i++)
#define all(ar) begin(ar), end(ar)
void chmin(ll &a, ll b) { a = min(a, b); }
void solve() {
ll n, a, b;
cin >> n >> a >> b;
chmin(a, b);
vector<vector<int>> g(n);
rep(i, 0, n - 1) {
ll u, v;
cin >> u >> v;
u--;
v--;
g[u].push_back(v);
g[v].push_back(u);
}
auto dfs = [&](auto self, ll v, ll p) -> pair<ll, ll> {
vector<pair<ll, ll>> ch;
for(int u : g[v]) {
if(u != p) {
ch.push_back(self(self, u, v));
}
}
if(ch.empty()) return {0, 0};
for(auto &[f, s] : ch) {
s += a;
}
sort(all(ch), [&](pair<ll, ll> p1, pair<ll, ll> p2) {
return p1.second - p1.first < p2.second - p2.first;
});
vector<ll> res(2, 1LL << 60);
ll s1 = 0;
for(auto [f, s] : ch) s1 += f;
res[(ch.size() + 1) % 2] = s1 + (ch.size() / 2) * b;
rep(i, 0, ch.size()) {
s1 -= ch[i].first;
s1 += ch[i].second;
chmin(res[(ch.size() - i) % 2], s1 + ((ch.size() - i - 1) / 2) * b);
}
// cout << v + 1 << " " << res[0] << " " << res[1] << endl;
return {res[0], res[1]};
};
int r = 0;
while(g[r].size() > 1) r++;
auto [f, s] = dfs(dfs, r, -1);
cout << f << endl;
}
int main() {
int t = 1;
// cin >> t;
while(t--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
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: 3584kb
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: 3584kb
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: 0
Accepted
time: 0ms
memory: 3584kb
input:
10 165074331 854297934 6 2 2 7 9 8 2 9 9 10 6 3 6 4 5 6 6 1
output:
825371655
result:
ok 1 number(s): "825371655"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
9 719441223 227056392 4 6 9 2 5 3 1 4 6 8 1 9 1 7 3 1
output:
227056392
result:
ok 1 number(s): "227056392"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
10 216399993 137522662 9 6 1 2 2 9 4 1 10 3 7 5 5 4 3 7 2 8
output:
137522662
result:
ok 1 number(s): "137522662"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
10 796722415 144928611 9 10 6 4 2 7 5 1 3 2 6 5 3 9 1 8 6 3
output:
289857222
result:
ok 1 number(s): "289857222"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
9 377925753 230747764 1 3 8 5 5 1 6 8 7 2 7 4 6 7 7 9
output:
230747764
result:
ok 1 number(s): "230747764"
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 3712kb
input:
1000 322954853 561443729 978 218 369 277 32 327 665 398 950 674 723 693 426 803 188 866 857 272 644 704 419 303 884 872 178 742 884 903 499 104 832 692 585 636 215 68 369 911 672 796 908 852 971 948 497 825 319 193 524 845 94 651 669 210 529 963 326 877 56 310 707 447 722 388 881 945 605 757 140 521...
output:
157055265578
result:
wrong answer 1st numbers differ - expected: '156210605808', found: '157055265578'