QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#699869#5439. Meet in the MiddleNityackeWA 0ms18012kbC++203.8kb2024-11-02 11:01:592024-11-02 11:02:01

Judging History

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

  • [2024-11-02 11:02:01]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:18012kb
  • [2024-11-02 11:01:59]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=1e5+5,M=5e5+5;
namespace IO{
	inline char gc(){
	static const int Rlen=1<<18|1;static char buf[Rlen],*p1,*p2;
	return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
	}
	template<typename T>T get_integer(){
		char c;bool f=false;while(!isdigit(c=gc()))f=c=='-';T x=c^48;
		while(isdigit(c=gc()))x=((x+(x<<2))<<1)+(c^48);return f?-x:x;
	}
	inline int gi(){return get_integer<int>();}
	char obuf[(int)(2e7+7)],*oh=obuf;
	inline void prt(char c){*oh++=c;}
	inline void prt(const char *s){
		while(*s)*oh++=*s++;
	}
	template<typename T>void prt(T a){
		static char ch[23];int tl=0;
		if(a<0)*oh++='-',a=-a;
		do ch[++tl]=a%10;while(a/=10);
		while(tl)*oh++=ch[tl--]^48;
	}
	template<typename T,class ...Args>
	void prt(T a,Args...args){
		prt(a),prt(args...);
	}
	struct obuf_flusher{
		~obuf_flusher(){fwrite(obuf,1,oh-obuf,stdout);}
	}Flusher;
}using namespace IO;
int T,n,q,ans[M];
vector<array<int,2>>Tr1[N],Tr2[N],Q[N];
namespace Tr{
	int st[17][N],dfn[N],dn,dis[N];
	inline int get(int x,int y){return dfn[x]<dfn[y]?x:y;}
	inline void dfs(int x,int fa){
		st[0][dfn[x]=++dn]=fa;
		for(auto v:Tr2[x])
			if(v[0]!=fa) dis[v[0]]=dis[x]+v[1],dfs(v[0],x);
	}
	inline void init(){
		dn=0,dfs(1,0);
		for(int j=1;j<17;++j)
			for(int i=1;i+(1<<j)-1<=n;++i) st[j][i]=get(st[j-1][i],st[j-1][i+(1<<(j-1))]);
	}
	inline int lca(int u,int v){
		if(u==v) return u;
		if((u=dfn[u])>(v=dfn[v])) swap(u,v);
		int L=__lg(v-(u++));
		return get(st[L][u],st[L][v-(1<<L)+1]);
	}
	inline int dist(int u,int v){return dis[u]+dis[v]-2*dis[lca(u,v)];}
}using Tr::dist;
int st[N],rev[N],ed[N],dn,dep[N];
inline void pre(int x,int fa){
	st[x]=++dn,rev[dn]=x;
	for(auto v:Tr1[x])
		if(v[0]!=fa) dep[v[0]]=dep[x]+v[1],pre(v[0],x);
	ed[x]=dn;
}
inline int calc(int a,int b,int c,int d){return a==b?0:dist(a,b)+c+d;}
namespace ST{
	#define node array<int,4>
	node t[N<<2];
	int tag[N<<2];
	#define k1 (k<<1)
	#define k2 (k<<1|1)
	#define mid ((l+r)>>1)
	array<int,2>pos[5];
	inline node operator+(node A,node B){
		node C=A;
		pos[0]={A[0],A[2]},pos[1]={A[1],A[3]},pos[2]={B[0],B[2]},pos[3]={B[1],B[3]};
		for(int i=0;i<=3;++i)
			for(int j=i+1;j<=3;++j)
				if(calc(pos[i][0],pos[j][0],pos[i][1],pos[j][1])>calc(C[0],C[1],C[2],C[3])) C={pos[i][0],pos[j][0],pos[i][1],pos[j][1]};
		return C;
	}
	inline void up(int k){t[k]=t[k1]+t[k2];}
	inline void build(int k=1,int l=1,int r=n){
		tag[k]=0;
		if(l==r) return t[k]={rev[l],rev[l],dep[rev[l]],dep[rev[l]]},void();
		build(k1,l,mid),build(k2,mid+1,r),up(k);
	}
	inline void add(int k,int v){t[k][2]+=v,t[k][3]+=v,tag[k]+=v;}
	inline void push(int k){if(tag[k]) add(k1,tag[k]),add(k2,tag[k]),tag[k]=0;}
	inline void change(int L,int R,int val,int k=1,int l=1,int r=n){
		if(L<=l&&R>=r) return add(k,val);
		push(k);
		if(L<=mid) change(L,R,val,k1,l,mid);
		if(R>mid) change(L,R,val,k2,mid+1,r);
		up(k);
	}
}
inline void solve(int x,int fa){
	node now=ST::t[1];
	for(auto v:Q[x]) ans[v[1]]=max(calc(now[0],v[0],now[2],0),calc(now[1],v[0],now[3],0));
	for(auto v:Tr1[x])
		if(v[0]!=fa){
			ST::change(1,n,v[1]),ST::change(st[v[0]],ed[v[0]],-2*v[1]);
			solve(v[0],x);
			ST::change(1,n,-v[1]),ST::change(st[v[0]],ed[v[0]],2*v[1]);
		}
}
inline void solve(){
	n=gi(),dn=0;
	for(int i=1;i<=n;++i) Tr1[i].clear(),Tr2[i].clear(),Q[i].clear();
	for(int i=1,u,v,w;i<n;++i) u=gi(),v=gi(),w=gi(),Tr1[u].pb({v,w}),Tr1[v].pb({u,w});
	for(int i=1,u,v,w;i<n;++i) u=gi(),v=gi(),w=gi(),Tr2[u].pb({v,w}),Tr2[v].pb({u,w});
	q=gi();
	for(int i=1,u,v;i<=q;++i) u=gi(),v=gi(),Q[u].pb({v,i});
	Tr::init(),pre(1,0),ST::build(),solve(1,0);
	for(int i=1;i<=q;++i) prt(ans[i],'\n');
}
signed main(){
	T=1;
	while(T--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 18012kb

input:

3 4
1 2 1
2 3 2
1 2 2
2 3 1
1 1
1 2
2 1
2 2

output:

12

result:

wrong answer 1st numbers differ - expected: '6', found: '12'