QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#878852#9696. Analysisucup-team5177#WA 0ms5976kbC++23895b2025-02-01 18:16:232025-02-01 18:16:25

Judging History

This is the latest submission verdict.

  • [2025-02-06 00:45:32]
  • hack成功,自动添加数据
  • (/hack/1517)
  • [2025-02-01 18:16:25]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 5976kb
  • [2025-02-01 18:16:23]
  • 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;
    std::vector<int> tp;
    for(int i=hd[n];i;i=nxt[i]) {
        if(to[i]==ff) continue;
        dfs(to[i],n);
        tp.push_back(f[to[i]]);
    }
    std::sort(tp.begin(),tp.end());
    for(int i=0;i+1<tp.size();i+=2) {
        aq+=std::min(1ll*A*(tp[i]+tp[i+1]),(long long)B);
    }
    if(tp.size()%2==1) ma=tp[tp.size()]-1;
    f[n]=ma+1;
}
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: 5972kb

input:

5 100 1000
1 2
2 3
3 4
4 5

output:

0

result:

ok 1 number(s): "0"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 5976kb

input:

5 100 200
1 2
1 3
2 4
2 5

output:

200

result:

wrong answer 1st numbers differ - expected: '100', found: '200'