QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#879005#9696. Analysisucup-team5177#WA 0ms8016kbC++231.2kb2025-02-01 19:43:042025-02-01 19:43:15

Judging History

This is the latest submission verdict.

  • [2025-02-06 00:45:32]
  • hack成功,自动添加数据
  • (/hack/1517)
  • [2025-02-01 19:43:15]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 8016kb
  • [2025-02-01 19:43:04]
  • Submitted

answer

#include <bits/stdc++.h>
#define LL long long
#define INF_LL (0x3f3f3f3f3f3f3f3f)
LL f[500009],as=-INF_LL;
int N,A,B,dg[500009],hd[500009],to[1000009],nxt[1000009],k;
void l(int u,int v) {
    to[++k]=v;nxt[k]=hd[u];hd[u]=k;
}
void dfs(int n,int ff) {
    LL a=-INF_LL,b=-INF_LL,xx=-INF_LL,yy=-INF_LL;
    for(int i=hd[n];i;i=nxt[i]) {
        if(to[i]==ff) continue;
        dfs(to[i],n);
        LL c=std::max(std::max(0ll,a)+f[to[i]]+A,b+f[to[i]]+A-B);
        LL d=std::max(std::max(0ll,a)+f[to[i]]+A,b+f[to[i]]+A);
        a=std::max(a,c);
        b=std::max(b,d);
    }
    b=std::max(b,0ll);
    f[n]=std::max(a,b-B);
    as=std::max(as,f[n]);
    //if(as==200) printf("%d\n",n);
}
signed main(void) {
    scanf("%d %d %d",&N,&A,&B);
    if(N<=2) {
        printf("0");
        return 0;
    }
    for(int i=1;i<N;i++) {
        int x,y;
        scanf("%d %d",&x,&y);
        l(x,y);
        l(y,x);
        dg[x]++;
        dg[y]++;
    }
    int rt=4742848%N+1;
//    for(int i=1;i<=N;i++) {
  //      if(dg[i]>=2) {
    //        rt=i;
  //          break;
  //      }
   // }
    dfs(rt,0);
  //  printf("%d %lld\n",rt,f[4][0]);
    LL ans=1ll*A*(N-1)-B-as;
    printf("%lld",ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 8016kb

input:

5 100 1000
1 2
2 3
3 4
4 5

output:

100

result:

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