QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#878732#9696. Analysisucup-team5177#WA 0ms5976kbC++23880b2025-02-01 17:11:162025-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:18]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 5976kb
  • [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'