QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#878324 | #9696. Analysis | ucup-team5234# | WA | 1ms | 3584kb | C++23 | 1.1kb | 2025-02-01 14:47:42 | 2025-02-01 14:47:48 |
Judging History
This is the latest submission verdict.
- [2025-02-06 00:45:32]
- hack成功,自动添加数据
- (/hack/1517)
- [2025-02-01 14:47:42]
- Submitted
answer
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
int main(){
ll N, A, B;
cin >> N >> A >> B;
if(N <= 2){
cout << 0 << "\n";
return 0;
}
vector<vector<int>> G(N);
for(int i = 0; i < N - 1; i ++){
int u,v;
cin >> u >> v;
u--;v--;
G[u].push_back(v);
G[v].push_back(u);
}
ll ans = 0;
vector<ll> V;
auto dfs = [&](auto f, int cur, int pre, int len) -> void {
if(G[cur].size() >= 3){
// cout << cur << " " << pre << " " << len << endl;
ans += min(A * len, B);
V.push_back(min(A * len, B));
return;
}
for(auto e : G[cur]){
if(pre == e)continue;
f(f, e, cur, len + 1);
}
};
for(int i = 0; i < N; i++){
if(G[i].size() == 1)
dfs(dfs, i, -1, 0);
}
sort(V.begin(), V.end(), greater<int>());
for(int i = 0; i < min(2, (int)V.size()); i++){
ans -= V[i];
}
cout << ans << endl;
}
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: 1ms
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: -100
Wrong Answer
time: 0ms
memory: 3328kb
input:
10 133494816 109943166 10 8 5 3 1 2 8 9 8 5 2 4 8 7 8 6 10 1
output:
329829498
result:
wrong answer 1st numbers differ - expected: '219886332', found: '329829498'