QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#878732 | #9696. Analysis | ucup-team5177# | WA | 0ms | 5976kb | C++23 | 880b | 2025-02-01 17:11:16 | 2025-02-01 17:11:18 |
Judging History
This is the latest submission verdict.
- [2025-02-06 00:45:32]
- hack成功,自动添加数据
- (/hack/1517)
- [2025-02-01 17:11:16]
- Submitted
answer
#include <bits/stdc++.h>
long long aq,ans;
int N,A,B,hd[500009],to[1000009],nxt[1000009],k,f[500009];
void l(int u,int v) {
to[++k]=v;nxt[k]=hd[u];hd[u]=k;
}
void dfs(int n,int ff) {
int ma=0;
for(int i=hd[n];i;i=nxt[i]) {
if(to[i]==ff) continue;
dfs(to[i],n);
ma=std::max(ma,f[to[i]]);
}
f[n]=ma+1;
for(int i=hd[n];i;i=nxt[i]) {
if(to[i]==ff) continue;
if(ma==f[to[i]]) ma=-1;
else {
aq+=std::min(1ll*A*f[to[i]],(long long)B);
}
}
}
signed main(void) {
scanf("%d %d %d",&N,&A,&B);
for(int i=1;i<N;i++) {
int x,y;
scanf("%d %d",&x,&y);
l(x,y);
l(y,x);
}
ans=0x3f3f3f3f3f3f;
for(int i=1;i<=N;i++) {
aq=0;
dfs(i,0);
ans=std::min(ans,aq);
}
printf("%lld",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5916kb
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: 5976kb
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: 5972kb
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'