QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#124229#5439. Meet in the Middle___WA 33ms51944kbC5.8kb2023-07-14 14:01:592023-07-14 14:02:03

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 14:02:03]
  • 评测
  • 测评结果:WA
  • 用时:33ms
  • 内存:51944kb
  • [2023-07-14 14:01:59]
  • 提交

answer

#include<stdio.h>
#define ll long long
#define N 200010
#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[M];
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[++pcta]=x;
	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]=pcta;
	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[++pctb]=x;
	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]=pctb;
	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;
	if(y.d>x.d)res=y;res.flag=0;
	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(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(x.x,y.x)+x.ax+y.ax>res.d){
		res.d=calb(x.x,y.x)+x.ax+y.ax;
		res.x=x.x;res.y=y.x;
		res.ax=x.ax;res.ay=y.ax;
		res.xid=x.xid;res.yid=y.xid;
	}
	if(calb(x.y,y.y)+x.ay+y.ay>res.d){
		res.d=calb(x.y,y.y)+x.ay+y.ay;
		res.x=x.y;res.y=y.y;
		res.ax=x.ay;res.ay=y.ay;
		res.xid=x.yid;res.yid=y.yid;
	}
	res.flag=0;
	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=0;
		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; 
		if(l==r)a[k].d=0;
		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){
		int y=ea[i].y;
		change(1,1,n,1,n,ea[i].s);
		change(1,1,n,dfsa[y]+1,dfsa[y]+sizea[y]-1,-2*ea[i].s);
		dfs2(y,x);
		change(1,1,n,1,n,-ea[i].s);
		change(1,1,n,dfsa[y]+1,dfsa[y]+sizea[y]-1,2*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: 24056kb

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: 24032kb

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: 22036kb

input:

2 1
1 2 1
1 2 1
1 2

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 28ms
memory: 51944kb

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:

647838384844
626539793176
514273941704
637066393138
472546379596
645842915960
641537859258
573604504956
644081575470
803875451466
674370549986
734764046916
744862815441
763778393516
553499885160
526743824759
610373719514
689550247042
549161302822
726811438160
653134244120
666761991962
701575393972
6...

result:

ok 50000 numbers

Test #5:

score: 0
Accepted
time: 30ms
memory: 51780kb

input:

10000 50000
5314 8843 137901358
5314 4153 459134340
5314 8667 933926892
4153 6504 330487798
4153 8880 750362377
4153 5990 874275912
4153 546 563436331
5990 6216 902348875
8843 3101 669215553
6216 8138 732343176
8667 8675 581114294
6504 7416 127778711
546 4239 282695908
6504 9455 549237168
5314 8340 ...

output:

464564968641
331633000004
565299667784
484694871646
570451097836
417492802442
372302349684
638725688107
386235986078
355738655551
462027769535
558485994764
524714144289
450157947013
432701214095
494566741391
529031758638
637683369382
415646847933
344894296260
390294136162
527685175763
575151290175
3...

result:

ok 50000 numbers

Test #6:

score: 0
Accepted
time: 32ms
memory: 44188kb

input:

10000 50000
2808 2490 757309564
2808 9601 312271047
2808 4046 119325897
2808 4894 466822371
4894 1507 498399554
2490 5982 84088145
9601 1251 149019541
2808 6681 416590999
2808 6583 357757899
1251 3192 889947539
6583 9762 350572496
6681 22 597479070
5982 8744 263208242
8744 5281 49894126
1507 8806 30...

output:

1501072697023
2058806276380
2017086500812
2044250452467
1543567245539
1695101693278
1765462307870
2576423082091
2302805133490
2090282734929
2375783476943
1954788661090
2056530503168
2453153202726
1978028047409
2106220371212
2210163378358
2015714406862
1555876274751
2122832986951
2102262624814
169085...

result:

ok 50000 numbers

Test #7:

score: -100
Wrong Answer
time: 33ms
memory: 44388kb

input:

10000 50000
4064 7188 81750473
7188 8466 310631946
8466 2276 154981798
2276 7347 162965456
7188 464 806245243
464 2250 849189978
8466 641 734602751
8466 9246 225800419
4064 5267 191524437
2276 5292 192776095
2276 9036 414997994
9246 5470 362146726
2250 473 98496385
4064 7726 700294189
473 9503 42824...

output:

3589143478793
5241855728342
3397106617685
3432843859461
4511581985154
3649934075137
3020107625030
3297847713344
3894730366667
3030559097282
4824131552194
4821302024170
4471510161493
3291683748595
4954639576578
2961243269520
3659899432127
3421183608349
5229903358912
4408705330639
5171084851821
500158...

result:

wrong answer 5th numbers differ - expected: '4544481241003', found: '4511581985154'