QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#63852#5105. Hand of the Free MarkedQingyuTL 0ms0kbC++2.0kb2022-11-23 14:51:022022-11-23 14:51:03

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-23 14:51:03]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2022-11-23 14:51:02]
  • 提交

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);
		}
	}
}


詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

3 3 2 1 2

output:


result: