QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#355557#5102. Dungeon CrawlerInfinityNS#WA 1ms3920kbC++143.1kb2024-03-16 20:26:522024-03-16 20:26:53

Judging History

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

  • [2024-03-16 20:26:53]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3920kb
  • [2024-03-16 20:26:52]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define f first
#define s second
const int N=2e3+5,L=11;
vector<vector<pair<int,int>>> graf(N);
int up[N][L],dep[N];
ll wdep[N];
void dfs(int tr,int par){
    up[tr][0]=par;
    for(auto p:graf[tr]){
        if(p.f!=par){
            dep[p.f]=dep[tr]+1;
            wdep[p.f]=wdep[tr]+p.s;
            dfs(p.f,tr);
        }
    }
}
int g(int x,int k){
    for(int j=L-1;j>=0;j--){
        if((1<<j)<=k){
            k-=(1<<j);
            x=up[x][j];
        }
    }
    return x;
}
int lc(int a,int b){
    if(dep[a]<dep[b])swap(a,b);
    a=g(a,dep[a]-dep[b]);
    if(a==b)return a;
    for(int j=L-1;j>=0;j--){
        if(up[a][j]!=up[b][j]){
            a=up[a][j];
            b=up[b][j];
        }
    }
    return up[a][0];
}
ll aa[N];
ll subT[N];
void dfs3(int tr,int par){
    subT[tr]=wdep[tr];
    for(auto p:graf[tr]){
        if(p.f!=par){
            dfs3(p.f,tr);
            subT[tr]=max(subT[tr],subT[p.f]);
        }
    }
}
void dfs2(int tr,int par,ll a){
    aa[tr]=a;
    vector<int> deca;
    for(auto p:graf[tr]){
        if(p.f!=par){
            deca.pb(p.f);
        }
    }
    vector<ll> ww;
    for(auto p:deca){
        ww.pb(subT[p]);
    }
    ll trW=-1;
    for(int i=((int)ww.size())-2;i>=0;i--){
        ww[i]=max(ww[i],ww[i+1]);
    }
    for(int i=0;i<ww.size();i++){
        ll x=-1;
        if(i!=((int)ww.size())-1){
            x=ww[i+1];
        }
        x=max(x,trW);
        dfs2(deca[i],tr,x);
        trW=max(trW,ww[i]);
    }
}
const int Q=2e5+5;
ll ans[Q];
vector<pair<pair<int,int>,int>> qu[N];
int main(){
    int n,q;
    scanf("%i %i",&n,&q);
    ll w2=0;
    for(int i=1;i<n;i++){
        int u,v,w;
        scanf("%i %i %i",&u,&v,&w);
        w2+=w;
        w2+=w;
        u--;v--;
        graf[u].pb({v,w});
        graf[v].pb({u,w});
    }
    for(int i=0;i<q;i++){
        int s,k,t;
        scanf("%i %i %i",&s,&k,&t);
        s--;t--;k--;
        qu[s].pb({{k,t},i});
    }
    for(int i=0;i<n;i++){
        dep[i]=0;
        wdep[i]=0;
        dfs(i,i);
        for(int j=1;j<L;j++){
            for(int i=0;i<n;i++){
                up[i][j]=up[up[i][j-1]][j-1];
            }
        }
        dfs3(i,i);
        dfs2(i,i,0);
        for(auto p:qu[i]){
            int k=p.f.f,t=p.f.s;
            int ind=p.s;
            if(k==t){
                ans[ind]=subT[i];
            }
            else{
                int l=lc(k,t);
                if(l==t){
                    ans[ind]=-1;
                }
                else{
                    if(k==l){
                        ans[ind]=subT[i];
                    }
                    else{
                        int sl=g(k,dep[k]-dep[l]-1);
                        ans[ind]=aa[sl];
                    }
                }
            }
        }
    }
    for(int i=0;i<q;i++){
        if(ans[i]==-1){
            printf("impossible\n");
        }
        else{
            printf("%lld\n",w2-ans[i]);
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3920kb

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:

293
293
293
impossible
286

result:

wrong answer 1st lines differ - expected: '316', found: '293'