QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#334177#6111. Two PathsFISHER_WA 556ms61456kbC++146.3kb2024-02-21 12:33:312024-02-21 12:33:32

Judging History

你现在查看的是最新测评结果

  • [2024-02-21 12:33:32]
  • 评测
  • 测评结果:WA
  • 用时:556ms
  • 内存:61456kb
  • [2024-02-21 12:33:31]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
    int len=0;
    char ibuf[(1<<21)+1],*iS,*iT,out[(1<<25)+1];
    #if ONLINE_JUDGE
    #define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
    #else
    #define gh() getchar()
    #endif
    #define reg register
    inline int read(){
        reg char ch=gh();
        reg int x=0;
        reg char t=0;
        while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
        while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
        return t?-x:x;
    }
    inline void putc(char ch){
        out[len++]=ch;
    }
    template<class T>
    inline void write(T x){
        if(x<0)putc('-'),x=-x;
        if(x>9)write(x/10);
        out[len++]=x%10+48;
    }
    inline void flush(){
        fwrite(out,1,len,stdout);
        len=0;
    }
    inline char getc(){
        char ch=gh();
        while(ch<'A'||ch>'Z') ch=gh();
        return ch;
    }
}
using IO::read;
using IO::write;
using IO::flush;
using IO::getc;
using IO::putc;
#define pii pair<int,int>
#define mpr make_pair
#define fir first
#define sec second
const int N=2e5+10,Q=5e5+10;
int n,q,X,Y,head[N],fa[N],cnt;
ll dep[N],ans[Q],mx[N];
bool vis[N];
struct Edge{
    int to,nxt,w;
}a[N<<1];
inline void add(int u,int v,int w){
    a[++cnt]={v,head[u],w};
    head[u]=cnt;
}
struct Query{
    int u,v,a,b;
}qr[Q];
inline void dfs0(int x,int fa){
    for(int i=head[x];i;i=a[i].nxt){
        int t=a[i].to;
        if(t==fa) continue;
        dep[t]=dep[x]+a[i].w;
        dfs0(t,x);
    }
}
namespace ST{
    int dfn[N],lg[N],tim,st[19][N];
    vector<pii>son[N];
    inline void dfs(int x,int f){
        st[0][dfn[x]=++tim]=f;
        mx[x]=dep[x];
        for(int i=head[x];i;i=a[i].nxt){
            int t=a[i].to;
            if(t==f) continue;
            dep[t]=dep[x]+a[i].w,fa[t]=x;
            dfs(t,x);
            mx[x]=max(mx[x],mx[t]);
            son[x].push_back(mpr(dfn[t],t));
        }
    }
    inline int cmp(int x,int y){
        return dep[x]<dep[y]?x:y;
    }
    inline int LCA(int x,int y){
        if(x==y) return x;
        x=dfn[x],y=dfn[y];
        if(x>y) swap(x,y);
        x++;
        int i=lg[y-x+1],p=1<<i;
        return cmp(st[i][x],st[i][y-p+1]);
    }
    inline ll dis(int u,int v){
        return dep[u]+dep[v]-dep[LCA(u,v)]*2;
    }
    inline int find(int x,int y){
        return (*(--upper_bound(son[x].begin(),son[x].end(),mpr(dfn[y],N)))).sec;
    }
    struct Line{
        int a,b;
        Line(int x=0,int y=0){ a=x,b=y; }
        inline friend bool operator<(const Line &a,const Line &b){
            return dis(a.a,a.b)<dis(b.a,b.b);
        }
        inline friend Line operator+(const Line &a,const Line &b){
            return max({a,b,Line(a.a,b.a),Line(a.a,b.b),Line(a.b,b.a),Line(a.b,b.b)});
        }
    }s[N];
    inline void dfs2(int x,int f){
        s[x]=Line(x,x);
        for(int i=head[x];i;i=a[i].nxt){
            int t=a[i].to;
            if(t==f) continue;
            dfs2(t,x);
            s[x]=s[x]+s[t];
        }
    }
    inline void init(int x){
        dep[x]=fa[x]=tim=0;
        for(int i=1;i<=n;i++)
            son[i].clear();
        dfs(x,0);
        for(int i=1;(1<<i)<=n;i++)
            for(int j=1;j+(1<<i)-1<=n;j++)
                st[i][j]=cmp(st[i-1][j],st[i-1][j+(1<<i-1)]);
        for(int i=2;i<=n;i++)
            lg[i]=lg[i>>1]+1;
        dfs2(x,0);
    }
}
using ST::find;
using ST::init;
using ST::Line;
using ST::LCA;
using ST::dis;
int id[N];
ll pr[N],sf[N],prs[N],sfs[N],pmx[N];
inline void dfs(int x,int fa){
    for(int i=head[x];i;i=a[i].nxt){
        int t=a[i].to;
        if(t==fa) continue;
        id[t]=id[x];
        dfs(t,x);
    } 
}
int main(){
//  freopen("path1.in","r",stdin);
//  freopen("path1.ans","w",stdout);
    srand(time(0));
    n=read(),q=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        add(u,v,w),add(v,u,w);
    }
    for(int i=1;i<=q;i++){
        int u=read(),v=read(),A=read(),B=read();
        qr[i]={u,v,A,B};
    }
    dfs0(1,0);
    ll mxd=0;
    for(int i=1;i<=n;i++)
        if(dep[i]>mxd) mxd=dep[i],X=i;
    dep[X]=mxd=0;
    dfs0(X,0);
    for(int i=1;i<=n;i++)
        if(dep[i]>mxd) mxd=dep[i],Y=i;
    init(X);
    for(int i=1;i<=q;i++){
        int u=qr[i].u,v=qr[i].v,a=qr[i].a,b=qr[i].b;
        int l=LCA(u,v);
        if(l!=v){
            Line tmp=ST::s[find(l,v)];
            ans[i]=max(ans[i],a*dep[u]+b*max(dis(v,tmp.a),dis(v,tmp.b)));
        }
        if(l!=u){
            Line tmp=ST::s[find(l,u)];
            ans[i]=max(ans[i],b*dep[v]+a*max(dis(u,tmp.a),dis(u,tmp.b)));
        }
    }
    init(Y);
    for(int i=1;i<=q;i++){
        int u=qr[i].u,v=qr[i].v,a=qr[i].a,b=qr[i].b;
        int l=LCA(u,v);
        if(l!=v){
            Line tmp=ST::s[find(l,v)];
            ans[i]=max(ans[i],a*dep[u]+b*max(dis(v,tmp.a),dis(v,tmp.b)));
        }
        if(l!=u){
            Line tmp=ST::s[find(l,u)];
            ans[i]=max(ans[i],b*dep[v]+a*max(dis(u,tmp.a),dis(u,tmp.b)));
        }
    }
    vector<int>vec;
    vec.push_back(0);
    for(int i=X;i;i=fa[i])
        vec.push_back(i),vis[i]=1,id[i]=vec.size()-1;
    if(vec.size()<n){
        for(int i=1;i<vec.size();i++){
            ll v=0;
            for(int j=head[vec[i]];j;j=a[j].nxt){
                int t=a[j].to;
                if(vis[t]) continue;
                v=max(v,mx[t]-dep[vec[i]]);
                id[t]=i,dfs(t,vec[i]);
            }
            pr[i]=dep[X]-dep[vec[i]]+v,sf[i]=dep[vec[i]]+v;
            prs[i]=dep[X]-dep[vec[i]],sfs[i]=dep[vec[i]];
        }
        for(int i=1;i<=q;i++){
            int u=qr[i].u,v=qr[i].v,a=qr[i].a,b=qr[i].b;
            if(id[u]>id[v]) swap(u,v),swap(a,b);
            int l=id[u]+1,r=id[v]-1;
            if(l<r){
                ll mx=0;
                pmx[l-1]=0;
                for(int j=l;j<=r;j++)
                    pmx[j]=max(pmx[j-1],pr[j]);
                for(int k=l+1;k<=r;k++)
                    mx=max(mx,a*pmx[k-1]+b*sf[k]);
                ans[i]=max(ans[i],mx+a*(dep[u]-dep[X])+b*(dep[v]-dep[vec[r+1]]*2));
            }
        }
    }
    for(int i=1;i<=q;i++)
        write(ans[i]),putc('\n');
    flush();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 9988kb

input:

6 4
1 2 4
2 5 5
2 3 7
3 6 5
3 4 4
1 4 1 1
1 4 2 1
5 6 1 1
5 6 1 10

output:

18
32
18
160

result:

ok 4 number(s): "18 32 18 160"

Test #2:

score: 0
Accepted
time: 0ms
memory: 10212kb

input:

2 1
1 2 1
1 2 1 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 0ms
memory: 10184kb

input:

2 10
1 2 2
1 2 1 1
1 2 1 2
1 2 1 3
1 2 2 1
1 2 2 2
1 2 3 1
1 2 3 2
1 2 3 3
1 2 2 3
1 2 1 3

output:

0
0
0
0
0
0
0
0
0
0

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 58ms
memory: 28916kb

input:

10 500000
4 5 576
5 8 218
1 10 678
1 9 2540
7 8 2023
2 7 5510
2 9 8454
4 6 22
3 9 5248
2 5 35782 82142
1 2 95412 85188
4 5 82466 22193
3 6 22169 67901
4 10 67229 30987
1 10 68282 17858
1 8 53726 3246
5 8 13913 74110
2 8 30052 7204
1 4 95255 48216
2 5 41392 98997
3 8 8435 5947
1 5 22067 21610
7 9 343...

output:

674365186
1454303268
477920681
1359445921
1501996827
1320778726
889342640
1582045824
426346196
1792561801
789005461
166905972
478560756
71705653
343648830
901237204
420263788
1710700661
309792440
335240094
1852278021
1679904905
1055408048
1644275016
563316675
602184744
873340490
815015664
1356022267...

result:

ok 500000 numbers

Test #5:

score: 0
Accepted
time: 96ms
memory: 29796kb

input:

100 500000
4 63 6394
57 91 2108
5 52 9292
6 63 3151
52 62 1006
13 19 8138
42 59 6102
3 95 275
36 80 8426
20 84 7879
32 100 4423
71 89 9590
55 98 240
46 100 7470
70 92 7417
43 54 6092
24 41 230
93 94 6591
8 92 2558
34 63 7534
4 36 5620
17 93 987
35 96 1288
42 68 6280
72 89 9818
43 57 8266
26 62 2431
...

output:

30730511688
35868047826
94569561805
103860674856
108734641138
103921529851
151172279864
108994447520
79859941598
90637244010
113651189677
26614889256
54138181416
163935808262
43257729984
101945300646
27547811269
67543514171
84292164869
59484837480
117300068794
77146438694
27400485192
55424042658
628...

result:

ok 500000 numbers

Test #6:

score: 0
Accepted
time: 556ms
memory: 61456kb

input:

200000 500000
83239 106513 1257
142726 196994 1263
95614 142588 7488
88575 193932 8123
31396 180633 1564
37559 131657 927
143893 157390 740
117889 182920 7831
103309 142289 6864
15478 36228 2717
5896 6815 5902
42275 184396 2646
21903 63571 8966
23873 42450 2721
36540 46154 9467
155293 161123 8588
54...

output:

5966882576104305
7271792958583645
8570461339781342
9614114352538144
6712681170527500
9409581586879995
6304678086998919
6559831613756394
4016495625693024
4381351843519688
4971908463803118
8759545709797016
11418325924391126
8912046248703475
10780907424911508
3112723787504739
9395431732704804
851233289...

result:

ok 500000 numbers

Test #7:

score: -100
Wrong Answer
time: 69ms
memory: 29044kb

input:

10 500000
7 8 6474
3 4 6652
4 5 5193
6 9 457
5 9 3937
1 7 7261
2 5 6472
6 8 6967
3 10 8997
2 9 77462 28703
3 7 31026 16732
2 6 39340 36431
6 9 95641 333
4 8 17377 97247
2 4 20769 98147
4 6 425 42124
4 8 53119 54974
2 4 49307 3731
1 7 13417 95608
7 8 36330 40656
6 10 16594 36336
1 6 47819 1121
1 3 93...

output:

2723123845
841480408
1828727322
1988211389
2006138424
2972774483
878701873
1811610573
1614909795
3697830616
1573037298
1336010492
685083521
3657916506
2557058802
3370810317
3011684921
850332000
2124928512
3326043566
1360831395
1603107540
3131147303
1037179764
1973141216
1587191713
747094784
36277104...

result:

wrong answer 18th numbers differ - expected: '862077669', found: '850332000'