QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#217645 | #5102. Dungeon Crawler | ucup-team1004# | WA | 1ms | 4668kb | C++14 | 2.2kb | 2023-10-17 07:47:10 | 2023-10-17 07:47:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
if(x.empty())return out<<"[]";
out<<'['<<x[0];
for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
cerr<<x<<' ',debug(y...);
}
const int N=2e3+10;
int n,m;
vector<pair<int,int> >to[N];
struct Path{
int fa[N],top[N],siz[N],son[N],dep[N];
ll dis[N],f[N],g[N];
#define v e.first
#define w e.second
void dfs1(int u){
dep[u]=dep[fa[u]]+1,siz[u]=1;
f[u]=dis[u];
for(auto e:to[u])if(v^fa[u]){
fa[v]=u,dis[v]=dis[u]+w,dfs1(v);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
f[u]=max(f[u],f[v]);
}
}
int dft,dfn[N],pos[N];
void dfs2(int u,int t){
top[u]=t,pos[dfn[u]=++dft]=u;
if(son[u])dfs2(son[u],t);
for(auto e:to[u])if(v^fa[u]&&v^son[u])dfs2(v,v);
}
void dfs3(int u){
ll fi=g[u],se=fi;
for(auto e:to[u])if(v^fa[u]){
if(f[v]>fi)fi=f[v];
else se=max(se,f[v]);
}
for(auto e:to[u])if(v^fa[u]){
g[v]=f[v]==fi?se:fi;
dfs3(v);
}
}
#undef v
#undef w
void init(int rt){
dfs1(rt),dfs2(rt,rt),dfs3(rt);
}
int LCA(int u,int v){
for(;top[u]^top[v];u=fa[top[u]]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
}
return dep[u]<dep[v]?u:v;
}
int jump(int u,int k){
for(;k>dep[u]-dep[top[u]];u=fa[top[u]]){
k-=dep[u]-dep[top[u]]+1;
}
return pos[dfn[u]-k];
}
}T[N];
int main(){
scanf("%d%d",&n,&m);
ll sum=0;
for(int i=1,u,v,w;i<n;i++){
scanf("%d%d%d",&u,&v,&w);
to[u].push_back({v,w}),to[v].push_back({u,w});
sum+=w*2;
}
for(int i=1;i<=n;i++)T[i].init(i);
for(int rt,u,v;m--;){
scanf("%d%d%d",&rt,&u,&v);
int t=T[rt].LCA(u,v);
if(v==t){
puts("impossible");
}else if(u==t){
printf("%lld\n",sum-T[rt].f[rt]);
}else{
int x=T[rt].jump(u,T[rt].dep[u]-T[rt].dep[t]-1);
// debug(rt,u,v,t,x,T[rt].g[x]);
printf("%lld\n",min(sum-T[rt].g[x],T[rt].dis[u]+sum-T[u].f[u]));
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4668kb
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 323
result:
wrong answer 5th lines differ - expected: '314', found: '323'