QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#692504#5439. Meet in the MiddletobieWA 4ms38708kbC++144.9kb2024-10-31 14:38:022024-10-31 14:38:30

Judging History

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

  • [2024-10-31 14:38:30]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:38708kb
  • [2024-10-31 14:38:02]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=1e5+9;
typedef long long ll;
int Read()
{
	int x=0;char ch=getchar();
	while(!('0'<=ch&&ch<='9')) ch=getchar();
	while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
}
void Write(ll x)
{
	if(x<=9) return putchar(x+'0'),void();
	Write(x/10),putchar(x%10+'0');
}
int n,Q;
struct Tree{

vector<int> to[N],dist[N];
void Add_edge(int u,int v,int w)
{
	to[u].push_back(v);
	to[v].push_back(u);
	dist[u].push_back(w);
	dist[v].push_back(w);
}
int dep[N],fa[N],dfn[N],dfncnt=0;
ll len[N];
int st[22][N],lg_[N];
int Max_(int u,int v){return dep[u]<dep[v]?u:v;}
void dfs(int u,int f)
{
	dep[u]=dep[f]+1;
	fa[u]=f;
	dfn[u]=++dfncnt;
	st[0][dfncnt]=u;
	for(int i=0,v;i<to[u].size();i++)
	if((v=to[u][i])!=f) len[v]=len[u]+dist[u][i],dfs(v,u);
}
inline void ycl()
{
	dfs(1,0);
	for(int i=1;(1<<i)<=n;i++)
	for(int j=1;j+(1<<i)-1<=n;j++)
	st[i][j]=Max_(st[i-1][j],st[i-1][j+(1<<(i-1))]);
	lg_[0]=-1;
	for(int i=1;i<=n;i++) lg_[i]=lg_[i>>1]+1;
}
inline int Lca(int u,int v)
{
	if(u==v) return u;
	if(dfn[u]>dfn[v]) swap(u,v);
	int k=lg_[dfn[v]-dfn[u]];
	return fa[Max_(st[k][dfn[u]+1],st[k][dfn[v]-(1<<k)+1])];
}
inline ll Dist(int u,int v)
{
	return len[u]+len[v]-2*len[Lca(u,v)];
}

void Clear()
{
	for(int i=1;i<=n;i++) to[i].clear(),dist[i].clear();
	for(int i=1;i<=n;i++) dep[i]=fa[i]=dfn[i]=lg_[i]=len[i]=0;
	dfncnt=0;
}

};
Tree tr1,tr2;

struct info{
	int u,v;
	ll wu,wv,len;
	info(){}
	info(int u_,int v_,ll wu_,ll wv_,ll len_){u=u_,v=v_,wu=wu_,wv=wv_,len=len_;}
};
inline info operator+ (info &x,info &y)
{
	info ans=x;
	ll d;
	if(y.len>ans.len) ans=y;
	
	d=tr1.Dist(x.u,y.u)+x.wu+y.wu;
	if(d>ans.len) ans=info(x.u,y.u,x.wu,y.wu,d);
	d=tr1.Dist(x.u,y.v)+x.wu+y.wv;
	if(d>ans.len) ans=info(x.u,y.v,x.wu,y.wv,d);
	d=tr1.Dist(x.v,y.u)+x.wv+y.wu;
	if(d>ans.len) ans=info(x.v,y.u,x.wv,y.wu,d);
	d=tr1.Dist(x.v,y.v)+x.wv+y.wv;
	if(d>ans.len) ans=info(x.v,y.v,x.wv,y.wv,d);
	return ans;
}
inline info Merge(info &x,int u,ll wu)
{
	info ans=x;
	ll d;
	d=(wu<<1);
	if(d>ans.len) ans=info(u,u,wu,wu,d);
	d=tr1.Dist(x.u,u)+x.wu+wu;
	if(d>ans.len) ans=info(x.u,u,x.wu,wu,d);
	d=tr1.Dist(x.v,u)+x.wv+wu;
	if(d>ans.len) ans=info(x.v,u,x.wv,wu,d);
	return ans;
}

vector<int> to[N],dis[N];
void Add_edgeB(int u,int v,int w)
{
	to[u].push_back(v);
	to[v].push_back(u);
	dis[u].push_back(w);
	dis[v].push_back(w);
}
int vis[N],rt_,tcnt;
int siz[N],mxsiz[N];
void getrt(int u,int f)
{
	siz[u]=1,mxsiz[u]=0;
	for(int i=0;i<to[u].size();i++)
	{
		int v=to[u][i];
		if(v==f||vis[v]) continue;
		getrt(v,u);
		siz[u]+=siz[v];
		mxsiz[u]=max(mxsiz[u],siz[v]);
	}
	mxsiz[u]=max(mxsiz[u],tcnt-siz[u]);
	if(mxsiz[u]<mxsiz[rt_]) rt_=u;
}
info ss;
void dfs2(int u,int f,ll d)
{
	ss=Merge(ss,u,d);
	for(int i=0;i<to[u].size();i++)
	{
		int v=to[u][i];
		if(v==f||vis[v]) continue;
		dfs2(v,u,d+dis[u][i]);
	}
}

info pre[N],suf[N];

info zj[N],zj2[N];

vector<int> rt2[N];

void calc(int u)
{
	for(int i=0;i<to[u].size();i++)
	{
		int v=to[u][i];
		ss=info(u,u,0,0,0);
		if(vis[v])
		{
			pre[i]=suf[i]=ss;
			continue;
		}
		dfs2(v,u,dis[u][i]);
		pre[i]=suf[i]=ss;
	}
	for(int i=1;i<to[u].size();i++) pre[i]=pre[i]+pre[i-1];
	for(int i=(int)(to[u].size())-2;i>=0;i--) suf[i]=suf[i]+suf[i+1];
	
	for(int i=0;i<to[u].size();i++)
	{
		int v=to[u][i];
		if(vis[v]) continue;
		v=rt2[u][i];
		zj[v]=info(u,u,0,0,0);
		if(i>0) zj[v]=zj[v]+pre[i-1];
		if(i+1<to[u].size()) zj[v]=zj[v]+suf[i+1];
	}
	
	zj2[u]=suf[0];
}
int nxt[N];
void work(int u)
{
	vis[u]=1;
	for(int i=0;i<to[u].size();i++)
	{
		int v=to[u][i];
		if(vis[v])
		{
			rt2[u].push_back(0);
			continue;
		}
		tcnt=mxsiz[rt_=0]=siz[v];
		getrt(v,u);
		nxt[rt_]=u;
		rt2[u].push_back(rt_);
	}
	calc(u);
	for(int i=0;i<to[u].size();i++)
	if(rt2[u][i]) work(rt2[u][i]);
}

void chkmax(ll &x,ll y){if(y>=x) x=y;}
void solve(int A,int B)
{
	ll ans=0;
	chkmax(ans,tr1.Dist(zj2[B].u,A)+zj2[B].wu);
	chkmax(ans,tr1.Dist(zj2[B].v,A)+zj2[B].wv);
	int B0=B;
	while(nxt[B0])
	{
		ll dd=tr2.Dist(B,nxt[B0]);
		chkmax(ans,dd+tr1.Dist(zj[B0].u,A)+zj[B0].wu);
		chkmax(ans,dd+tr1.Dist(zj[B0].v,A)+zj[B0].wv);
		B0=nxt[B0];
	}
	Write(ans);putchar('\n');
}
void Clear()
{
	for(int i=1;i<=n;i++) to[i].clear(),rt2[i].clear(),dis[i].clear();
	for(int i=1;i<=n;i++) nxt[i]=vis[i]=0;
	tr1.Clear();tr2.Clear();
}


void mian()
{
	Clear();
	n=Read();
	for(int i=1;i<n;i++)
	{
		int u,v,w;
		u=Read(),v=Read(),w=Read();
		tr1.Add_edge(u,v,w);
	}
	for(int i=1;i<n;i++)
	{
		int u,v,w;
		u=Read(),v=Read(),w=Read();
		tr2.Add_edge(u,v,w);
		Add_edgeB(u,v,w);
	}
	
	tr1.ycl();tr2.ycl();
	tcnt=mxsiz[rt_=0]=n;
	getrt(1,0);
	work(rt_);
	
	Q=Read();
	while(Q--)
	{
		int x,y;
		x=Read(),y=Read();
		solve(x,y);
	}
}

signed main()
{
	int T=1;
	while(T--) mian();
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 38708kb

input:

3 4
1 2 1
2 3 2
1 2 2
2 3 1
1 1
1 2
2 1
2 2

output:

5

result:

wrong answer 1st numbers differ - expected: '6', found: '5'