QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#373156 | #5102. Dungeon Crawler | RobeZH# | RE | 1ms | 3616kb | C++23 | 3.9kb | 2024-04-01 04:38:27 | 2024-04-01 04:38:28 |
Judging History
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 ...