QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#373156#5102. Dungeon CrawlerRobeZH#RE 1ms3616kbC++233.9kb2024-04-01 04:38:272024-04-01 04:38:28

Judging History

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

  • [2024-04-01 04:38:28]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3616kb
  • [2024-04-01 04:38:27]
  • 提交

answer

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
// #include<atcoder/all>
#define FR(i,n) for(int i=0;i<n;++i)
#define eb emplace_back
#define st first
#define nd second
#define x1 fxxkcjb
#define y1 fxxkyzc
#define x2 fxxkzzy
#define y2 fxxknitit
using namespace std;
namespace R=ranges;
template<typename T>
using func=function<T>;
template<typename T>
using vec=vector<T>;
using ll=long long;
using ld=long double;
using i128=__int128;
using pll=pair<ll,ll>;
const int mod=998244353;
void sol(){
    int n,q;cin>>n>>q;
    vector g(n,vector<pll>());
    
    int total=0;
    FR(i,n-1){
        int x,y,z;cin>>x>>y>>z;--x,--y;
        g[x].eb(y,z),g[y].eb(x,z);
        total+=2*z;
    }
    vector f(11,vector<int>(n,-1));
    vector<ll>DIS(n),dep(n);
    func<void(int)>build=[&](int x){
        for(int i=1;i<11;++i)f[i][x]=f[i-1][x]==-1?-1:f[i-1][f[i-1][x]];
        for(auto[y,z]:g[x])if(y!=f[0][x]){
            f[0][y]=x;
            DIS[y]=DIS[x]+z;
            dep[y]=dep[x]+1;
            build(y);
        }
    };
    DIS[0]=dep[0]=0;
    build(0);
    auto lca=[&](int x,int y){
        if(dep[x]<dep[y])swap(x,y);
        for(int i=10;~i;--i)if(f[i][x]!=-1&&dep[f[i][x]]>=dep[y])x=f[i][x];
        if(x==y)return x;
        for(int i=10;~i;--i)if(f[i][x]!=f[i][y])x=f[i][x],y=f[i][y];
        return f[0][x];
    };
    auto dis=[&](pll u){
        return DIS[u.st]+DIS[u.nd]-2*DIS[lca(u.st,u.nd)];
    };
    auto upd=[&](pll&u,pll v){
        if(dis(u)<dis(v))u=v;
    };
    auto merge=[&](pll u,pll v){
        auto[a,b]=u;
        auto[c,d]=v;
        pll ret=u;
        upd(ret,v);
        upd(ret,{a,c});
        upd(ret,{a,d});
        upd(ret,{b,c});
        upd(ret,{b,d});
        // too slow?
        return ret;
    };
    vector<pll>ind(n),otd(n);
    func<void(int)>dfs=[&](int x){
        ind[x]={x,x};
        for(auto[y,z]:g[x])if(y!=f[0][x]){
            dfs(y);
            ind[x]=merge(ind[x],ind[y]);
        }
    };
    dfs(0);
    func<void(int)>dfs2=[&](int x){
        pll tmp=merge(otd[x],{x,x});
        vector<int>c;
        for(auto[y,z]:g[x])if(y!=f[0][x])c.eb(y);
        vector<pll>tmps(c.size());
        FR(i,c.size())tmps[i]=tmp,tmp=merge(tmp,ind[c[i]]);
        tmp=merge(otd[x],{x,x});
        for(int i=c.size()-1;~i;--i){
            otd[c[i]]=merge(tmp,tmps[i]);
            dfs2(c[i]);
            tmp=merge(tmp,ind[c[i]]);
        }
    };
    auto mxdis=[&](int x,pll u){return max(dis({x,u.st}),dis({x,u.nd}));};
    otd[0]={0,0};//not correct but should work
    dfs2(0);
    FR(tim,q){
        int s,k,t;cin>>s>>k>>t;--s,--k,--t;
        if(dis({s,k})==dis({s,t})+dis({t,k})){ //trap is on s->k
            cout<<"impossible\n";
            continue;
        }
        if(dis({s,t})==dis({s,k})+dis({k,t})){ //key is on s->t
            cout<<total-mxdis(s,ind[0])<<"\n";
            continue;
        }
        int trip;
        {
            trip=lca(s,k);
            int tmp=lca(s,t);
            if(dep[tmp]<dep[trip])trip=tmp;
            tmp=lca(k,t);
            if(dep[tmp]<dep[trip])trip=tmp;
        }
        assert(trip!=k);
        pll sside,kside;
        if(lca(trip,k)==trip){
            //k is inside trip tree
            int ptr=k;
            for(int i=10;~i;--i)if(f[i][ptr]!=-1&&dep[f[i][ptr]]>dep[trip])ptr=f[i][ptr];
            assert(f[0][ptr]==trip);
            sside=otd[ptr];
            kside=ind[ptr];
        }else{
            //k is outside trip
            sside=ind[trip];
            kside=otd[trip];
        }
        int mx1=mxdis(s,sside),mx2=mxdis(k,kside)-dis({k,trip})+dis({s,trip});
        cout<<total-max(mx1,mx2)<<"\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    sol();
    return 0;
}
/*
5 4
1 2 3
1 3 1
3 4 4
3 5 2
1 2 4
1 4 2
5 2 1
4 3 1

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3616kb

input:

22 5
1 2 7
2 3 5
3 4 8
3 6 6
3 7 3
2 5 6
5 8 2
8 9 11
2 10 16
1 11 12
11 12 4
11 13 9
1 14 25
14 15 4
15 16 5
15 17 6
15 18 1
15 19 8
14 20 7
20 21 9
20 22 17
1 19 9
1 9 19
1 8 9
1 9 8
2 22 11

output:

316
293
293
impossible
314

result:

ok 5 lines

Test #2:

score: -100
Runtime Error

input:

100 100
1 2 289384
2 3 930887
2 4 692778
4 5 636916
4 6 747794
4 7 238336
4 8 885387
8 9 760493
8 10 516650
8 11 641422
8 12 202363
8 13 490028
8 14 368691
8 15 520060
8 16 897764
16 17 513927
16 18 180541
16 19 383427
16 20 89173
16 21 455737
16 22 5212
16 23 595369
16 24 702568
16 25 956430
16 26 ...

output:


result: