QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#217645#5102. Dungeon Crawlerucup-team1004#WA 1ms4668kbC++142.2kb2023-10-17 07:47:102023-10-17 07:47:10

Judging History

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

  • [2023-10-17 07:47:10]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4668kb
  • [2023-10-17 07:47:10]
  • 提交

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'