QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#695491#5439. Meet in the MiddlelarryyuWA 3ms19980kbC++203.9kb2024-10-31 20:08:392024-10-31 20:08:43

Judging History

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

  • [2024-10-31 20:08:43]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:19980kb
  • [2024-10-31 20:08:39]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ls x<<1
#define rs x<<1|1
int t,n,q,cnt1,cnt2;
int dep[100010],id[200020],val[200020],fi[100010],st[200020][20];
int dis[100010],dfn[100010],siz[100010],no[100010],ans[500050];
vector<pii> v[100010];
struct tre{
	int tot;
	int head[100010];
	struct edge{
		int to,next,w;
	}e[200020];
	void add(int x,int y,int z){
		e[++tot]=edge{y,head[x],z};
		head[x]=tot;
	}
	void init(){
		for(int i=1;i<=n;i++) head[i]=0;
		tot=0;
	}
}t1,t2;
int getl(int l,int r){
	if(r<l) swap(l,r);
	int len=log2(r-l+1);
	int x=st[l][len],y=st[r-(1<<len)+1][len];
	if(val[x]<val[y]) return id[x];
	return id[y];
}
int calc(int x,int y){
	int lca=getl(fi[x],fi[y]);
	return dep[x]+dep[y]-2*dep[lca];
}
struct tree{
	int x,y,adx,ady,tag;
	friend tree operator+(tree a,tree b){
		tree c;
		int v1=calc(a.x,a.y)+a.adx+a.ady;
		int v2=calc(b.x,b.y)+b.adx+b.ady;
		int v3=calc(a.x,b.y)+a.adx+b.ady;
		int v4=calc(a.y,b.x)+a.ady+b.adx;
		int v5=calc(a.x,b.x)+a.adx+b.adx;
		int v6=calc(a.y,b.y)+a.ady+b.ady;
		int val=max(max(v1,max(v2,v3)),max(v4,max(v5,v6)));
		if(val==v1){
			c=tree{a.x,a.y,a.adx,a.ady,0};
		}else if(val==v2){
			c=tree{b.x,b.y,b.adx,b.ady,0};
		}else if(val==v3){
			c=tree{a.x,b.y,a.adx,b.ady,0};
		}else if(val==v4){
			c=tree{a.y,b.x,a.ady,b.adx,0};
		}else if(val==v5){
			c=tree{a.x,b.x,a.adx,b.adx,0};
		}else {
			c=tree{a.y,b.y,a.ady,b.ady,0};
		}
		return c;
	}
}tr[400040];
void lazy(int x,int v){
	tr[x].tag+=v;
	tr[x].adx+=v,tr[x].ady+=v;
}
void pushdown(int x){
	if(!tr[x].tag) return ;
	lazy(ls,tr[x].tag);
	lazy(rs,tr[x].tag);
	tr[x].tag=0;
}
void build(int x,int l,int r){
	if(l==r){
		tr[x]=tree{no[l],no[r],dis[no[l]],dis[no[r]],0};
		return ;
	}
	int mid=l+r>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	tr[x]=tr[ls]+tr[rs];
}
void update(int x,int l,int r,int L,int R,int v){
	if(l>=L&&r<=R) return lazy(x,v),void();
	pushdown(x);
	int mid=l+r>>1;
	if(L<=mid) update(ls,l,mid,L,R,v);
	if(R>=mid+1) update(rs,mid+1,r,L,R,v);
	tr[x]=tr[ls]+tr[rs];
}
void dfs1(int x,int fax){
	fi[x]=++cnt1;
	id[cnt1]=x,val[cnt1]=dep[x];
	for(int i=t2.head[x];i;i=t2.e[i].next){
		int y=t2.e[i].to,w=t2.e[i].w;
		if(y==fax) continue;
		dep[y]=dep[x]+w;
		dfs1(y,x);
		id[++cnt1]=x,val[cnt1]=dep[x];
	}
}
void dfs2(int x,int fax){
	dfn[x]=++cnt2,no[cnt2]=x;
	siz[x]=1;
	for(int i=t1.head[x];i;i=t1.e[i].next){
		int y=t1.e[i].to,w=t1.e[i].w;
		if(y==fax) continue;
		dis[y]=dis[x]+w;
		dfs2(y,x);
		siz[x]+=siz[y];
	}
}
void dfs3(int x,int fax){
	for(auto i:v[x]){
		int x=tr[1].x,y=tr[1].y,dx=tr[1].adx,dy=tr[1].ady;
		int lx=calc(i.first,x)+dx,ly=calc(i.first,y)+dy;
		if(lx>ly) ans[i.second]=lx;
		else ans[i.second]=ly;
	}
	for(int i=t1.head[x];i;i=t1.e[i].next){
		int y=t1.e[i].to,w=t1.e[i].w;
		if(y==fax) continue;
		update(1,1,n,1,n,w);
		update(1,1,n,dfn[y],dfn[y]+siz[y]-1,-2*w);
		dfs3(y,x);
		update(1,1,n,1,n,-w);
		update(1,1,n,dfn[y],dfn[y]+siz[y]-1,2*w);
	}
}
void init(){
	t1.init(),t2.init();
	cnt1=0,cnt2=0;
	for(int i=1;i<=n;i++) v[i].clear();
}
void solve(){
	init();
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		t1.add(x,y,z),t1.add(y,x,z);
	}
	for(int i=1;i<n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		t2.add(x,y,z),t2.add(y,x,z);
	}
	cin>>q;
	for(int i=1;i<=q;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back({y,i});
	}
	dfs1(1,0);
	for(int i=1;i<=cnt1;i++){
		st[i][0]=i;
	}
	for(int j=1;j<=18;j++){
		for(int i=1;i+(1<<j)-1<=cnt1;i++){
			int x=st[i][j-1],y=st[i+(1<<j-1)][j-1];
			if(val[x]<val[y]){
				st[i][j]=x;
			}else st[i][j]=y;
		}
	}
	dfs2(1,0);
	build(1,1,n);
	dfs3(1,0);
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<'\n';
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	// cin>>t;
	// while(t--){
		solve();
	// }
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 19980kb

input:

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

output:

5

result:

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