/ Randle /

记录详情

Wrong Answer

/in/foo.cc: In function 'int grab(int, int, int, int, int)':
/in/foo.cc:82:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if (y-x>1) ret+=pre[tr][y-1]-pre[tr][x]; tr^=1;
   ^~
/in/foo.cc:82:44: note: ...this statement, but the latter is misleadingly indented as if it is guarded by the 'if'
   if (y-x>1) ret+=pre[tr][y-1]-pre[tr][x]; tr^=1;
                                            ^~
# 状态 耗时 内存占用
#1 Wrong Answer 2ms 328.0 KiB
#2 Wrong Answer 2ms 332.0 KiB
#3 Wrong Answer 2ms 332.0 KiB
#4 Wrong Answer 73ms 13.965 MiB
#5 Wrong Answer 72ms 13.992 MiB
#6 Wrong Answer 72ms 13.992 MiB
#7 Wrong Answer 172ms 13.914 MiB
#8 Wrong Answer 166ms 13.996 MiB
#9 Wrong Answer 171ms 14.02 MiB
#10 Wrong Answer 166ms 14.016 MiB

代码

#include <cstdio>
#include <algorithm>
#define bi(x) (1<<x)
#define rep(i,j,k) for (i=j;i<=k;i++)
#define down(i,j,k) for (i=j;i>=k;i--)
const int N=1e5+5,K=17;
using namespace std;
int cs,n,m,x,y,z,u,v,c,g,i,j,l,ml,ans,SUM;
int En,fst[N],dep[N],nxt[N*2],to[N*2],val[N*2],sum[N],jp[N][K+1];
int tm,b[N*2],bl[N],br[N],pre[2][N*2],up[N];
void add(int u,int v,int c) {
	En++; nxt[En]=fst[u]; fst[u]=En; to[En]=v; val[En]=c;
}
void dfs(int x,int fa)
{
	int i,j,l,r;
	jp[x][0]=fa;
	rep(j,1,K) jp[x][j]=jp[ jp[x][j-1] ][j-1];
	dep[x]=dep[fa]+1;
	for (j=fst[x];j;j=nxt[j])
		if (to[j]!=fa)
			dfs(to[j],x),sum[x]+=sum[to[j]]+val[j];
		else up[x]=val[j];
		
	bl[x]=tm+1;
	for (j=fst[x];j;j=nxt[j])
		if (to[j]!=fa) b[++tm]=val[j]+sum[to[j]];
		else b[++tm]=SUM-sum[x];
	br[x]=tm; l=bl[x]; r=br[x];
	sort(b+l,b+r+1);
	reverse(b+l,b+r+1);	

	pre[1][l]=b[l]; pre[0][l]=0;
	if (l<r) pre[0][l+1]=b[l+1],pre[1][l+1]=b[l];

	rep(i,l+2,r) {
		pre[0][i]=pre[0][i-1],pre[1][i]=pre[1][i-1];
		if ((i-l+1)&1) pre[1][i]+=b[i];
		else pre[0][i]+=b[i];
	}
}
int lca(int u,int v)
{
	int j;
	if (dep[u]<dep[v]) swap(u,v);
	down(j,K,0)
		if (dep[ jp[u][j] ]>=dep[v]) u=jp[u][j];
	if (u==v) return u;
	down(j,K,0)
		if (jp[u][j]!=jp[v][j]) u=jp[u][j],v=jp[v][j];
	return jp[u][0];
}
int jump(int x,int d)
{
	int j;
	down(j,K,0)
		if (bi(j)<=d) x=jp[x][j],d-=bi(j);
	return x;
}
int erfen(int x,int l,int r)
{
	int mid;
	while (l<=r)
	{
		mid=(l+r)>>1;
		if (x==b[mid]) return mid;
		if (x>b[mid]) r=mid-1;
		else l=mid+1;	
	}
	return r+1;
}
int grab(int flg,int tr,int wh,int vl,int vr)
{
	int l=bl[wh],r=br[wh],x,y,ret=0;
	x=erfen(vl,l,r);
	y=erfen(vr,l,r);
	if (x==y) y++;
	if (x>y) swap(x,y);
	if (x>l) ret+=pre[tr][x-1];
	tr^=1;
	if (flg) {
		if (y-x>1) ret+=pre[tr][y-1]-pre[tr][x]; tr^=1;
		if (y<r) ret+=pre[tr][r]-pre[tr][y];
	}
	else if (x<r) ret+=pre[tr][r]-pre[tr][x];
	return ret;
}
int main()
{
	//freopen("b.in","r",stdin);
	//freopen("b1.out","w",stdout);
	scanf("%d%d",&n,&m);
	rep(i,1,n-1)
	{
		scanf("%d%d%d",&u,&v,&c);
		add(u,v,c); add(v,u,c);
		SUM+=c;
	}
	dfs(1,1);
	rep(cs,1,m)
	{
		scanf("%d%d",&u,&v);
		g=lca(u,v);
		l=dep[u]+dep[v]-dep[g]*2;
		ml=(l+1)/2;
		if (u==v) ans=pre[1][br[u]];
		else if (u==g) {
			if (jp[v][0]==u) ans=grab(0,0,v,up[v],0)+SUM-sum[v];
			else
			{
				z=jump(v,l-ml-1);
				x=jp[z][0];
				ans=grab(1,(l&1)^1,x,up[x],up[z])+SUM-sum[x];
			}
		}
		else if (v==g) {
			if (jp[u][0]==v) ans=grab(0,0,v,up[u],0)+sum[u]+up[u];
			else
			{
				z=jump(u,ml-1);
				x=jp[z][0];
				ans=grab(1,(l&1)^1,x,up[x],up[z])+sum[z]+up[z];
			}
		}
		else {
			if (ml<dep[u]-dep[g]) {
				z=jump(u,ml-1);
				x=jp[z][0];
				ans=grab(1,(l&1)^1,x,up[x],up[z])+sum[z]+up[z];
			}
			else
			if (ml>dep[u]-dep[g]) {
				z=jump(v,l-ml-1);
				x=jp[z][0];
				ans=grab(1,(l&1)^1,x,up[x],up[z])+SUM-sum[x];	
			}
			else {
				x=jump(u,ml-1);
				y=jump(v,l-ml-1);
				ans=grab(1,(l&1)^1,g,up[x],up[y])+sum[x]+up[x];
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}
/*
  N=1
  u=v
*/

信息

递交者
类型
递交
题目
树上角斗 T2
题目数据
下载
语言
C++
递交时间
2019-02-23 20:53:42
评测时间
2019-02-23 20:53:42
评测机
分数
0
总耗时
903ms
峰值内存
14.02 MiB