QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#124229 | #5439. Meet in the Middle | ___ | WA | 33ms | 51944kb | C | 5.8kb | 2023-07-14 14:01:59 | 2023-07-14 14:02:03 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'