QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#480643#5439. Meet in the MiddleyanshanjiahongCompile Error//C++204.2kb2024-07-16 17:05:072024-07-16 17:05:09

Judging History

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

  • [2024-07-16 17:05:09]
  • 评测
  • [2024-07-16 17:05:07]
  • 提交

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],eular[2*N],cntu,pose[N];
	ll lenf[N],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;
		eular[++cntu]=x,pose[x]=cntu;
		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];
			eular[++cntu]=x;
		}
	}
	int lg[2*N],st[2*N][20];
	void init(){
		lg[1]=0;
		rep(i,2,cntu)
		    lg[i]=lg[i/2]+1;
	}
	void build(){
		init();
		rep(i,1,cntu)
		    st[i][0]=dfn[eular[i]];
		rep(j,1,18){
			rep(i,1,cntu){
				st[i][j]=st[i][j-1];
				if(i+(1<<(j-1))<=cntu)st[i][j]=min(st[i][j],st[i+(1<<(j-1))][j-1]);
			}
		}
	}
	int query(int x,int y){
		if(x>y)swap(x,y);
		int len=y-x+1;
		return min(st[x][lg[len]],st[y-(1<<lg[len])+1][lg[len]]);
	}
	int lca(int x,int y){
		return nw[query(pose[x],pose[y])];
	}
	ll getdis(int x,int y){
		return dis[x]+dis[y]-2ll*dis[lca(x,y)];
	}
	void init_tree(){
		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);
		build();
	}
}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 nqp=1;
ll getdim(int x,int y){
//	printf("%lld %lld %lld\n",y,T1.dfn[y],SGT2.query(1,1,n,T1.dfn[y]));
	return T1.getdis(nqp,x)+T1.getdis(nqp,y)+T2.getdis(x,y);
}
struct seg1{
	int t[4*N][2];
	void pushup(int x){
		ll res=0;
		ll 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){
	if(v>0)nqp=x;
	else nqp=T1.fa[x][0];
	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,1);
	int l=SGT1.t[1][0],r=SGT1.t[1][1];
	for(auto j:q[x]){
	    ll valx=T1.getdis(l,nqp)+T2.getdis(l,j.fir);
	    ll valy=T1.getdis(r,nqp)+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,-1);
}
signed main(){
	read(n),read(m);
	T1.init_tree(),T2.init_tree();
	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

answer.code: In function ‘int main()’:
answer.code:181:9: error: ‘SGT2’ was not declared in this scope; did you mean ‘SGT1’?
  181 |         SGT2.build(1,1,n),SGT1.build(1,1,n);
      |         ^~~~
      |         SGT1