QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#480568 | #5439. Meet in the Middle | yanshanjiahong | WA | 456ms | 22760kb | C++14 | 4.0kb | 2024-07-16 16:38:16 | 2024-07-16 16:38:16 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
#define lowbit(i) i&-i
using namespace std;
typedef long long ll;
const int N=1e5+5,M=5e5+5,S=(1<<15)+5,inf=1e9+7,mo=1e9+7;
const double eps=1e-8;
void read(int &p){
int x=0,w=1;
char ch=0;
while(!isdigit(ch)){
if(ch=='-')w=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
p=x*w;
}
int n,m;
struct tree{
vector<pii>e[N];
int dfn[N],cntp,nw[N];
int fa[N][20],dep[N],sz[N],lenf[N];
ll dis[N];
void dfs(int x,int f){
fa[x][0]=f,dep[x]=dep[f]+1,sz[x]=1;
dfn[x]=++cntp,nw[cntp]=x;
rep(i,1,17)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(auto p:e[x]){
int j=p.fir,w=p.sec;
if(j==f)continue;
dis[j]=dis[x]+w,lenf[j]=w;
dfs(j,x),sz[x]+=sz[j];
}
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
repp(i,17,0)
if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
if(x==y)return x;
repp(i,17,0)
if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
ll getdis(int x,int y){
return dis[x]+dis[y]-2ll*dis[lca(x,y)];
}
void init(){
rep(i,1,n-1){
int x,y,w;
read(x),read(y),read(w);
e[x].push_back(mp(y,w)),e[y].push_back(mp(x,w));
}
dfs(1,0);
}
}T1,T2;
vector<pii>q[N];
struct seg2{
ll t[4*N];
void build(int x,int le,int ri){
if(le==ri){
t[x]=T1.dis[T1.nw[le]];
//printf("*%lld %lld\n",le,t[x]);
return;
}
int mid=(le+ri)>>1;
build(ls(x),le,mid),build(rs(x),mid+1,ri);
}
void modify(int x,int le,int ri,int ql,int qr,int v){
if(ql>qr)return;
if(ql<=le&&qr>=ri){
t[x]+=v;
return;
}
int mid=(le+ri)>>1;
if(ql<=mid)modify(ls(x),le,mid,ql,qr,v);
if(qr>mid)modify(rs(x),mid+1,ri,ql,qr,v);
}
ll query(int x,int le,int ri,int p){
if(le==ri)return t[x];
int mid=(le+ri)>>1;
if(p<=mid)return query(ls(x),le,mid,p)+t[x];
else return query(rs(x),mid+1,ri,p)+t[x];
}
}SGT2;
int getdim(int x,int y){
// printf("%lld %lld %lld\n",y,T1.dfn[y],SGT2.query(1,1,n,T1.dfn[y]));
return SGT2.query(1,1,n,T1.dfn[x])+SGT2.query(1,1,n,T1.dfn[y])+T2.getdis(x,y);
}
struct seg1{
int t[4*N][2];
void pushup(int x){
int res=0;
int nwv=getdim(t[ls(x)][0],t[ls(x)][1]);
if(nwv>res)t[x][0]=t[ls(x)][0],t[x][1]=t[ls(x)][1],res=nwv;
nwv=getdim(t[rs(x)][0],t[rs(x)][1]);
if(nwv>res)t[x][0]=t[rs(x)][0],t[x][1]=t[rs(x)][1],res=nwv;
rep(i,0,1){
rep(j,0,1){
nwv=getdim(t[ls(x)][i],t[rs(x)][j]);
if(nwv>res)t[x][0]=t[ls(x)][i],t[x][1]=t[rs(x)][j],res=nwv;
}
}//printf("!!!%lld\n",getdim(1,2));
}
void build(int x,int le,int ri){
if(le==ri){
t[x][0]=t[x][1]=T1.nw[le];
return;
}
int mid=(le+ri)>>1;
build(ls(x),le,mid),build(rs(x),mid+1,ri);
pushup(x);
//printf("%lld %lld %lld %lld\n",le,ri,t[x][0],t[x][1]);
}
void modify(int x,int le,int ri,int p){
if(le==ri)return;
int mid=(le+ri)>>1;
if(p<=mid)modify(ls(x),le,mid,p);
else modify(rs(x),mid+1,ri,p);
pushup(x);
}
}SGT1;
void update(int x,int v){
SGT2.modify(1,1,n,T1.dfn[x],T1.dfn[x]+T1.sz[x]-1,-1*v);
SGT2.modify(1,1,n,1,T1.dfn[x]-1,1*v);
SGT2.modify(1,1,n,T1.dfn[x]+T1.sz[x],n,1*v);
SGT1.modify(1,1,n,T1.dfn[x]),SGT1.modify(1,1,n,T1.dfn[x]+T1.sz[x]-1);
}
ll ans[M];
void dfs(int x,int f){
if(x!=1)update(x,T1.lenf[x]);
int l=SGT1.t[1][0],r=SGT1.t[1][1];
//printf("*%lld %lld\n",l,r);
for(auto j:q[x]){
ll valx=SGT2.query(1,1,n,T1.dfn[l])+T2.getdis(l,j.fir);
ll valy=SGT2.query(1,1,n,T1.dfn[r])+T2.getdis(r,j.fir);
ans[j.sec]=max(valx,valy);
}
for(auto j:T1.e[x]){
if(j.fir==f)continue;
dfs(j.fir,x);
}
if(x!=1)update(x,-T1.lenf[x]);
}
signed main(){
read(n),read(m);
T1.init(),T2.init();
rep(i,1,m){
int x,y;
read(x),read(y);
q[x].push_back(mp(y,i));
}
SGT2.build(1,1,n),SGT1.build(1,1,n);
dfs(1,0);
rep(i,1,m)
printf("%lld\n",ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 20236kb
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: 20312kb
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: 3ms
memory: 20292kb
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: 456ms
memory: 22760kb
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:
205429096925 268990890446 312021789775 227509909740 161140811376 227026824644 233950095636 371352353027 7321114767 46989821805 331536355019 253440950198 296989818959 139931696314 274103028218 77603204472 278874986324 250354656811 252959041722 79668339687 321635510930 292002254317 140169232831 132369...
result:
wrong answer 1st numbers differ - expected: '647838384844', found: '205429096925'