QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#124213 | #5439. Meet in the Middle | ___ | WA | 25ms | 38420kb | C++98 | 5.5kb | 2023-07-14 13:12:48 | 2023-07-14 13:12:51 |
Judging History
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'