QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#480528#5439. Meet in the MiddleyanshanjiahongWA 453ms22700kbC++144.0kb2024-07-16 16:22:312024-07-16 16:22:33

Judging History

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

  • [2024-07-16 16:22:33]
  • 评测
  • 测评结果:WA
  • 用时:453ms
  • 内存:22700kb
  • [2024-07-16 16:22:31]
  • 提交

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: 4ms
memory: 20220kb

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

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

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: 453ms
memory: 22700kb

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'