QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#621478#5439. Meet in the MiddlekaiyiWA 32ms35224kbC++144.6kb2024-10-08 14:47:272024-10-08 14:47:56

Judging History

This is the latest submission verdict.

  • [2024-10-08 14:47:56]
  • Judged
  • Verdict: WA
  • Time: 32ms
  • Memory: 35224kb
  • [2024-10-08 14:47:27]
  • Submitted

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+10;
int n,q;
vector<pair<int,int> >A[N];
vector<pair<int,int> >B[N];
vector<pair<int,int> >b[N];
int ans[N*5];

int A_dfn[N],B_dfn[N];
int dfn;
int e[N<<1],tot;
int ST[N<<1][20];
int p[N];
int rdis[N];//B 树到根的距离
int a[N],to_a[N];
int mn[N],mx[N];//A 树的子树区段
void pdfs(int u,int fa){
    B_dfn[u] = ++dfn;
    e[++tot] = B_dfn[u];
    p[B_dfn[u]] = tot;
    for(auto v:B[u]){
        if(v.first == fa)continue;
        rdis[v.first] = rdis[u] + v.second;
        pdfs(v.first,u);
        e[++tot] = B_dfn[u];
    }
}
void init(){
    for(int i=1;i<=tot;i++)ST[i][0] = e[i];
    for(int i=1;i<20;i++){
        for(int j=1;j<=tot;j++){
            ST[j][i] = ST[j][i-1];
            if(j+(1<<(i-1)) <= tot)ST[j][i] = min(ST[j][i-1],ST[j+(1<<(i-1))][i-1]);
        }
    }
}
int log(int len){return 63 - __builtin_clzll(len*1ull);}
int get_dis(int u,int v){
    if(u==v)return 0;
    //get lca
    int ret = 0;
    if(p[B_dfn[u]] > p[B_dfn[v]])swap(u,v);
    int k = log(p[B_dfn[v]] - p[B_dfn[u]] + 1);
    assert(k<20);
    int lca = min(ST[p[B_dfn[u]]][k],ST[p[B_dfn[v]] - (1<<k) + 1][k]);
    //get dis
    ret = rdis[u] + rdis[v] - 2*rdis[lca];
    return ret;
}

void dfs(int u,int fa){
    A_dfn[u] = ++dfn;
    to_a[dfn] = u;
    mn[u] = mx[u] = dfn;
    for(auto v:A[u]){
        if(v.first == fa)continue;
        a[v.first] = a[u] + v.second;
        dfs(v.first,u);
        mx[u] = max(mx[u],mx[v.first]);
    }
}

int p1[N<<2],p2[N<<2],w1[N<<2],w2[N<<2],lz[N<<2];

#define mid ((l+r)>>1)
#define ls (x<<1)
#define rs (x<<1|1)

void pushup(int x){
    int _p[4] = {p1[ls],p2[ls],p1[rs],p2[rs]};
    int _w[4] = {w1[ls],w2[ls],w1[rs],w2[rs]};
    int dis = 0,rp1 = 0,rp2 = 0,rw1 = 0,rw2 = 0;
    for(int i=0;i<3;i++){
        for(int j=i+1;j<4;j++){
            if(_p[i] == _p[j]){
                if(dis < _w[i]){
                    dis = _w[i];
                    rp1 = _p[i];rp2 = _p[j];
                    rw1 = _w[i];rw2 = _w[j];
                }
            }else{
                int d = get_dis(_p[i],_p[j]);
                if(dis < d + _w[i] + _w[j]){
                    dis = d + _w[i] + _w[j];
                    rp1 = _p[i];rp2 = _p[j];
                    rw1 = _w[i];rw2 = _w[j];
                }
            }
        }
    }
    p1[x] = rp1;p2[x] = rp2;
    w1[x] = rw1;w2[x] = rw2;
}
void pushdown(int x){
    int lazy = lz[x];
    lz[x] = 0;
    w1[ls] += lazy;w2[ls] += lazy;lz[ls] += lazy;
    w1[rs] += lazy;w2[rs] += lazy;lz[rs] += lazy;
}
void build(int x,int l,int r){
    if(l==r){
        p1[x] = p2[x] = to_a[l];
        w1[x] = w2[x] = a[to_a[l]];
        return ;
    }
    build(ls,l,mid);build(rs,mid+1,r);
    pushup(x);
    // cout<<x<<' '<<l<<' '<<r<<' '<<p1[x]<<' '<<p2[x]<<' '<<w1[x]<<' '<<w2[x]<<'\n';
}
void mdf(int x,int l,int r,int L,int R,int v){
    if(L<=l && r<=R){
        w1[x] += v;w2[x] += v;
        lz[x] += v;
        return ;
    }
    pushdown(x);
    if(L<=mid)mdf(ls,l,mid,L,R,v);
    if(R>mid)mdf(rs,mid+1,r,L,R,v);
    pushup(x);
}
void hg(int u,int fa){
    //statistics

    // cout<<u<<':'<<p1[1]<<' '<<p2[1]<<' '<<w1[1]<<' '<<w2[1]<<'\n';

    for(auto i:b[u]){
        ans[i.second] = max(get_dis(i.first,p1[1])+w1[1],get_dis(i.first,p2[1])+w2[1]);
    }
    for(auto v:A[u]){
        if(v.first==fa)continue;
        //in
        mdf(1,1,n,1,n,v.second);
        mdf(1,1,n,mn[v.first],mx[v.first],-2*v.second);
        hg(v.first,u);
        //out
        mdf(1,1,n,mn[v.first],mx[v.first],2*v.second);
        mdf(1,1,n,1,n,-v.second);
    }
}

void solve(){
    cin>>n>>q;
    for(int i=1,u,v,w;i<n;i++){
        cin>>u>>v>>w;
        A[u].push_back({v,w});
        A[v].push_back({u,w});
    }
    for(int i=1,u,v,w;i<n;i++){
        cin>>u>>v>>w;
        B[u].push_back({v,w});
        B[v].push_back({u,w});
    }
    for(int i=1,ta,tb;i<=q;i++){
        cin>>ta>>tb;
        b[ta].push_back({tb,i});
    }
    //预处理B树的树上距离
    pdfs(1,0);dfn=0;
    init();
    //线段树
    //求出根节点答案 build
    dfs(1,0);
    build(1,1,n);
    //换根

    hg(1,0);

    // cout<<p1[1]<<' '<<p2[1]<<' '<<w1[1]<<' '<<w2[1]<<endl;
    // cout<<get_dis(p1[1],p2[1]) + w1[1] + w2[1]<<endl;

    //输出
    for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int aqx = 1;
    //cin>>aqx;
    while(aqx--)solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 4
1 2 1
2 3 2
1 2 2
2 3 1
1 1
1 2
2 1
2 2

output:

6
4
5
3

result:

ok 4 number(s): "6 4 5 3"

Test #2:

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

input:

2 1
1 2 1
1 2 1
1 1

output:

2

result:

ok 1 number(s): "2"

Test #3:

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

input:

2 1
1 2 1
1 2 1
1 2

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: -100
Wrong Answer
time: 32ms
memory: 35224kb

input:

10000 50000
8101 5996 108427744
5996 7605 870838849
5996 5599 603303696
8101 3006 339377417
8101 6463 442516687
6463 5560 109174079
5560 4063 127596224
3006 1682 947915262
5996 1986 130416311
6463 5455 279771516
6463 2634 516688796
4063 3034 217886863
7605 5092 742375061
5599 2266 193804402
5092 140...

output:

605428585885
515786999416
341010677550
594656594179
364851767304
603433117001
601464348532
535915664344
578179670938
516161934444
634297039260
601246048146
712111878009
539592707192
513426374434
486670314033
504433652298
649476736316
509087792096
495771618350
582467592188
607963406540
529335429169
6...

result:

wrong answer 1st numbers differ - expected: '647838384844', found: '605428585885'