QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#124213#5439. Meet in the Middle___WA 25ms38420kbC++985.5kb2023-07-14 13:12:482023-07-14 13:12:51

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-14 13:12:51]
  • 评测
  • 测评结果:WA
  • 用时:25ms
  • 内存:38420kb
  • [2023-07-14 13:12:48]
  • 提交

answer

#include<stdio.h>
#define ll long long
#define N 100010
#define M 500010
#define int long long 
int maxx(int x,int y){return x>y?x:y;}
int minn(int x,int y){return x<y?x:y;}
ll maxl(ll x,ll y){return x>y?x:y;}
ll minl(ll x,ll y){return x<y?x:y;} 
int read(){
	char ch;int zf=1,res=0;
	while((ch=getchar())<48||ch>57)if(ch=='-')zf=!zf;res=(ch^48);
	while((ch=getchar())>=48&&ch<=57)res=(res<<3)+(res<<1)+(ch^48);
	return zf?res:(-res);
}
struct node1{
	int y,nxt;ll s;
}ea[N<<1],eb[N<<1];int staa[N],stab[N],cnta,cntb;
struct node2{
	int s,nxt;int id;
}ask[M];int stas[N],cnts;ll anss[N];
int lg2[N<<1];
int dfsa[N],dfsb[N],dcta,dctb;
ll adda[N],addb[N]; 
int sizea[N];
int oulaa[N<<1],oulab[N<<1],pcta,pctb,fstoulaa[N],fstoulab[N];
int depa[N],depb[N];
struct node3{
	int s,id;
}sa[N<<1][25],sb[N<<1][25];
struct node{
	int x,y;int xid,yid;ll ax,ay;ll d,flag;
}a[N<<2];
int n,q;
int dy[N],ndy[N];
int pbsta(int x){
	oulaa[x]=++pcta;
	sa[pcta][0].id=x;sa[pcta][0].s=depa[x];
	return 0;
}
int dfsa1(int x,int fa,ll S){
	adda[x]=adda[fa]+S;
	dfsa[x]=++dcta;
	dy[x]=dfsa[x];
	ndy[dfsa[x]]=x;
	depa[x]=depa[fa]+1;
	pbsta(x);
	sizea[x]=1;
	fstoulaa[x]=oulaa[x];
	for(int i=staa[x];i;i=ea[i].nxt)if(ea[i].y!=fa){
		dfsa1(ea[i].y,x,ea[i].s);
		pbsta(x);
		sizea[x]+=sizea[ea[i].y];
	}
	return 0;
}
int pbstb(int x){
	oulab[x]=++pctb;
	sb[pctb][0].id=x;sb[pctb][0].s=depb[x];
	return 0;
}
int dfsb1(int x,int fa,ll S){
	addb[x]=addb[fa]+S;
	dfsb[x]=++dctb;
	depb[x]=depb[fa]+1;
	pbstb(x);
	fstoulab[x]=oulab[x];
	for(int i=stab[x];i;i=eb[i].nxt)if(eb[i].y!=fa){
		dfsb1(eb[i].y,x,eb[i].s);
		pbstb(x);
	}
	return 0;
}
struct node3 mergest(struct node3 x,struct node3 y){
	if(x.s<=y.s)return x;
	else return y;
}
int finda(int x,int y){
	x=fstoulaa[x];y=fstoulaa[y];
	if(x>y){int p=x;x=y;y=p;}
	int p=lg2[y-x+1];
	return mergest(sa[x][p],sa[y-(1<<p)+1][p]).id;
}
int findb(int x,int y){
	x=fstoulab[x];y=fstoulab[y];
	if(x>y){int p=x;x=y;y=p;}
	int p=lg2[y-x+1];
	return mergest(sb[x][p],sb[y-(1<<p)+1][p]).id;
}
int yclst(){
	lg2[0]=-1;
	for(int i=1;i<=n+n;i++)lg2[i]=lg2[i>>1]+1;
	for(int h=1;(1<<h)<n+n;h++)
		for(int i=1;i+(1<<h)-1<n+n;i++){
			sa[i][h]=mergest(sa[i][h-1],sa[i+(1<<(h-1))][h-1]);	
			sb[i][h]=mergest(sb[i][h-1],sb[i+(1<<(h-1))][h-1]);	
		}
	return 0;
}
ll cala(int x,int y){
	return adda[x]+adda[y]-adda[finda(x,y)]*2;
}
ll calb(int x,int y){
	return addb[x]+addb[y]-addb[findb(x,y)]*2;
}
struct node merge(struct node x,struct node y){
	struct node res=x;res.flag=0;
	if(y.d>x.d)res=y;
	if(calb(x.x,y.y)+x.ax+y.ay>res.d){
		res.d=calb(x.x,y.y)+x.ax+y.ay;
		res.x=x.x;res.y=y.y;
		res.ax=x.ax;res.ay=y.ay;
		res.xid=x.xid;res.yid=y.yid;
	}
	if(calb(y.x,x.y)+y.ax+x.ay>res.d){
		res.d=calb(y.x,x.y)+y.ax+x.ay;
		res.x=y.x;res.y=x.y;
		res.ax=y.ax;res.ay=x.ay;
		res.xid=y.xid;res.yid=x.yid;
	}
	return res;
}
int pushdown(int,int,int,int);
int build(int k,int l,int r){
//	printf("A%d %d %d\n",k,l,r);
	if(l==r){
		a[k].x=a[k].y=ndy[l];
		a[k].ax=a[k].ay=adda[ndy[l]];
		a[k].xid=a[k].yid=ndy[l];
		a[k].flag=0;
		a[k].d=a[k].ax+a[k].ay;
		return 0;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	a[k]=merge(a[k<<1],a[k<<1|1]);
	return 0;
}
int change(int k,int l,int r,int x,int y,ll S){
	if(x>r||y<l||x>y)return 0;
	if(x<=l&&y>=r){
		ll p=S;
		a[k].ax+=p;
		a[k].ay+=p;
		a[k].d+=p*2;
		a[k].flag+=p; 
		return 0;
	}
	int mid=(l+r)>>1;
	pushdown(k,l,r,mid);
	change(k<<1,l,mid,x,y,S);
	change(k<<1|1,mid+1,r,x,y,S);
	a[k]=merge(a[k<<1],a[k<<1|1]);
	return 0;
}
struct node find(int k,int l,int r,int x,int y){
	if(x<=l&&y>=r)return a[k];
	int mid=(l+r)>>1;
	pushdown(k,l,r,mid);
	if(y<=mid)return find(k<<1,l,mid,x,y);
	if(x>mid)return find(k<<1|1,mid+1,r,x,y);
	return merge(find(k<<1,l,mid,x,y),find(k<<1|1,mid+1,r,x,y));
}
int pushdown(int k,int l,int r,int mid){
	if(a[k].flag){
		change(k<<1,l,mid,l,mid,a[k].flag);
		change(k<<1|1,mid+1,r,mid+1,r,a[k].flag);
		a[k]=merge(a[k<<1],a[k<<1|1]);
		a[k].flag=0;
	}
	return 0;
}

int mergea(int x,int y,ll S){
	ea[++cnta].y=y;
	ea[cnta].nxt=staa[x];
	staa[x]=cnta;
	ea[cnta].s=S;
	ea[++cnta].y=x;
	ea[cnta].nxt=staa[y];
	staa[y]=cnta;
	ea[cnta].s=S;
	return 0;
}
int mergeb(int x,int y,ll S){
	eb[++cntb].y=y;
	eb[cntb].nxt=stab[x];
	stab[x]=cntb;
	eb[cntb].s=S;
	eb[++cntb].y=x;
	eb[cntb].nxt=stab[y];
	stab[y]=cntb;
	eb[cntb].s=S;
	return 0;
}
int merges(int x,int s,int id){
	ask[++cnts].s=s;
	ask[cnts].nxt=stas[x];
	stas[x]=cnts;
	ask[cnts].id=id;
	return 0;
}
int dfs2(int x,int fa){
//	printf("B%d %d\n",x,fa); 
	for(int i=stas[x];i;i=ask[i].nxt){
		struct node p=find(1,1,n,1,n);
		anss[ask[i].id]=maxl((cala(x,p.x)+calb(p.x,ask[i].s)),(cala(x,p.y)+calb(p.y,ask[i].s)));
	}
	for(int i=staa[x];i;i=ea[i].nxt)if(ea[i].y!=fa){
		change(1,1,n,1,n,-2*ea[i].s);
		change(1,1,n,dfsa[x]+1,dfsa[x]+sizea[x]-1,ea[i].s);
		dfs2(ea[i].y,x);
		change(1,1,n,1,n,2*ea[i].s);
		change(1,1,n,dfsa[x]+1,dfsa[x]+sizea[x]-1,-ea[i].s);
	}
	return 0;
}
signed main(){
	n=read();q=read();
	for(int i=1;i<n;i++){
		int x,y,s;x=read();y=read();s=read();
		mergea(x,y,s);
	}
	for(int i=1;i<n;i++){
		int x,y,s;x=read();y=read();s=read();
		mergeb(x,y,s);
	}
	for(int i=1;i<=q;i++){
		int x,y;
		x=read();y=read();
		merges(x,y,i);
	}
	dfsa1(1,0,0);dfsb1(1,0,0);
	
	yclst();
//	puts("!!!");
	build(1,1,n);
	dfs2(1,0);
	for(int i=1;i<=q;i++)printf("%lld\n",anss[i]);
	return 0;



}
	






詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 15844kb

input:

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

output:

6
4
5
3

result:

ok 4 number(s): "6 4 5 3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 15852kb

input:

2 1
1 2 1
1 2 1
1 1

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: 0
Accepted
time: 0ms
memory: 13864kb

input:

2 1
1 2 1
1 2 1
1 2

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: -100
Wrong Answer
time: 25ms
memory: 38420kb

input:

10000 50000
8101 5996 108427744
5996 7605 870838849
5996 5599 603303696
8101 3006 339377417
8101 6463 442516687
6463 5560 109174079
5560 4063 127596224
3006 1682 947915262
5996 1986 130416311
6463 5455 279771516
6463 2634 516688796
4063 3034 217886863
7605 5092 742375061
5599 2266 193804402
5092 140...

output:

95631036482
283679808393
225063894124
191105893609
153383294828
199882416431
67554478429
245472841670
273476045981
260674169231
414927492837
353106340186
320961724050
297556110399
294056828011
267300767610
186472628123
115566866213
289718245673
183610155925
229233152729
469529118183
148116397938
274...

result:

wrong answer 1st numbers differ - expected: '647838384844', found: '95631036482'