QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#63852 | #5105. Hand of the Free Marked | Qingyu | TL | 0ms | 0kb | C++ | 2.0kb | 2022-11-23 14:51:02 | 2022-11-23 14:51:03 |
Judging History
answer
#include<bits/stdc++.h>
#define re register
#define ll long long
using namespace std;
inline int read(){
re int t=0;re char v=getchar();
while(v<'0')v=getchar();
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
return t;
}
const int M=998244353;
inline void add(re int &x,re int y){(x+=y)>=M?x-=M:x;}
inline int Mod(re int x){return x>=M?x-M:x;}
inline int ksm(re int x,re int y){
re int s=1;
while(y){
if(y&1)s=1ll*s*x%M;
x=1ll*x*x%M,y>>=1;
}
return s;
}
vector<int>E[2002],W[2002];
int dfn[2002][2002],n,m,siz[2002][2002],rt,fa[2002][2002],tim;
ll dis[2002][2002],sum,Mx[2002][2002];
inline void dfs(re int x,re int y){
siz[rt][x]=1,dfn[rt][x]=++tim,fa[rt][x]=y,Mx[rt][x]=dis[rt][x];
for(re int i=0;i<E[x].size();++i)
if(E[x][i]^y){
dis[rt][E[x][i]]=dis[rt][x]+W[x][i];
dfs(E[x][i],x);
siz[rt][x]+=siz[rt][E[x][i]];
Mx[rt][x]=max(Mx[rt][x],Mx[rt][E[x][i]]);
}
}
inline bool in(re int x,re int y,re int z){
return dfn[x][z]>=dfn[x][y]&&dfn[x][z]<dfn[x][y]+siz[x][y];
}
inline int lca(re int x,re int y,re int z){
while(y^z){
if(dfn[x][y]>dfn[x][z])y=fa[x][y];
else z=fa[x][z];
}
return y;
}
int main(){
n=read(),m=read();
for(re int i=1,x,y,z;i<n;++i){
x=read(),y=read(),z=read();
E[x].push_back(y),E[y].push_back(x);
W[x].push_back(z),W[y].push_back(z);
sum+=z;
}
for(re int i=1;i<=n;++i)rt=i,tim=0,dfs(i,i);
while(m--){
re int x=read(),y=read(),z=read();re ll mx=0;
if(in(x,y,z)){
for(re int i=1;i<=n;++i)mx=max(mx,dis[x][i]);
printf("%lld\n",sum+sum-mx);
}
else if(in(x,z,y))puts("impossible");
else{
re int o=lca(x,z,y),oy=y;
while(fa[x][y]^o)y=fa[x][y];
for(re int i=1;i<=n;++i)if(!in(x,y,i))mx=max(mx,dis[x][i]);
ll tmp=sum+sum-mx;int lst=0;
while(oy^o){
tmp=min(tmp,sum+sum-dis[x][oy]+dis[o][oy]*2);
for(auto z:E[oy])if(z^fa[x][oy]&&z^lst)tmp=min(tmp,sum+sum-Mx[x][z]+dis[o][oy]*2);
lst=oy,oy=fa[x][oy];
}
printf("%lld\n",tmp);
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
3 3 2 1 2