「BZOJ3924」[ZJOI2015] 幻想乡战略游戏

2015年5月1日7,6020

陈老师的博客：

http://wjmzbmr.com/archives/zjoi-2015-day-1%E9%A2%98%E8%A7%A3/

先贴个暴力。。。每次暴力转移重心。。。bzoj能过

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define mod 1000000007
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll ans,tot;
int n,m,cnt,id,rt=1;
int last[100005];
int fa[100005],size[100005],dep[100005],d[100005],bl[100005];
int pos[100005];
int sum[400005];
struct edge{
	int to,next,v;
}e[200005];
void insert(int u,int v,int w)
{
	e[++cnt]=(edge){v,last[u],w};last[u]=cnt;
	e[++cnt]=(edge){u,last[v],w};last[v]=cnt;
}
void modify(int k,int l,int r,int pos,int val)
{
	if(l==r){sum[k]+=val;return;}
	int mid=(l+r)>>1;
	if(pos<=mid)modify(k<<1,l,mid,pos,val);
	else modify(k<<1|1,mid+1,r,pos,val);
	sum[k]=sum[k<<1]+sum[k<<1|1];
}
int query(int k,int l,int r,int x,int y)
{
	if(l==x&&y==r)return sum[k];
	int mid=(l+r)>>1;
	int ans=0;
	if(x<=mid)ans+=query(k<<1,l,mid,x,min(y,mid));
	if(y>mid)ans+=query(k<<1|1,mid+1,r,max(x,mid+1),y);
	return ans;
}
void dfs(int x)
{
	size[x]=1;
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa[x])
		{
			fa[e[i].to]=x;
			dep[e[i].to]=dep[x]+1;
			d[e[i].to]=d[x]+e[i].v;
			dfs(e[i].to);
			size[x]+=size[e[i].to];
		}
}
void dfs2(int x,int cha)
{
	pos[x]=++id;bl[x]=cha;
	int k=0;
    for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa[x]&&size[e[i].to]>size[k])
			k=e[i].to;
	if(k)dfs2(k,cha);
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa[x]&&e[i].to!=k)
			dfs2(e[i].to,e[i].to);
}
int lca(int x,int y)
{
	while(bl[x]!=bl[y])
		if(dep[bl[x]]>dep[bl[y]])x=fa[bl[x]];
		else y=fa[bl[y]];
	return dep[x]<dep[y]?x:y;
}
int dis(int x,int y)
{
	return d[x]+d[y]-2*d[lca(x,y)];
}
ll cal(int x,int v)
{
	int t1,t2;
	if(x==fa[rt])
	{
		t1=query(1,1,n,pos[rt],pos[rt]+size[rt]-1);
		t2=tot-t1;
	}
	else 
	{
		t2=query(1,1,n,pos[x],pos[x]+size[x]-1);
		t1=tot-t2;
	}
	return ans+(ll)(t1-t2)*v;
}
void move(int x)
{
	ll mn=(ll)1e60,t;
	int id=0;
	for(int i=last[x];i;i=e[i].next)
	{
		t=cal(e[i].to,e[i].v);
		if(t<mn)mn=t,id=e[i].to;
	}
	if(mn<ans){rt=id;ans=mn;move(rt);}
}
int main()
{
	n=read();m=read();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read(),w=read();
		insert(u,v,w);
	}
	dfs(1);
	dfs2(1,1);
	while(m--)
	{
		int u=read(),e=read();
		ans+=(ll)e*dis(u,rt);
		tot+=e;modify(1,1,n,pos[u],e);
		move(rt);
		printf("%lld\n",ans);
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

#define mod 1000000007

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

ll ans,tot;

int n,m,cnt,id,rt=1;

int last[100005];

int fa[100005],size[100005],dep[100005],d[100005],bl[100005];

int pos[100005];

int sum[400005];

struct edge{

int to,next,v;

}e[200005];

void insert(int u,int v,int w)

{

e[++cnt]=(edge){v,last[u],w};last[u]=cnt;

e[++cnt]=(edge){u,last[v],w};last[v]=cnt;

}

void modify(int k,int l,int r,int pos,int val)

{

if(l==r){sum[k]+=val;return;}

int mid=(l+r)>>1;

if(pos<=mid)modify(k<<1,l,mid,pos,val);

else modify(k<<1|1,mid+1,r,pos,val);

sum[k]=sum[k<<1]+sum[k<<1|1];

}

int query(int k,int l,int r,int x,int y)

{

if(l==x&&y==r)return sum[k];

int mid=(l+r)>>1;

int ans=0;

if(x<=mid)ans+=query(k<<1,l,mid,x,min(y,mid));

if(y>mid)ans+=query(k<<1|1,mid+1,r,max(x,mid+1),y);

return ans;

}

void dfs(int x)

{

size[x]=1;

for(int i=last[x];i;i=e[i].next)

if(e[i].to!=fa[x])

{

fa[e[i].to]=x;

dep[e[i].to]=dep[x]+1;

d[e[i].to]=d[x]+e[i].v;

dfs(e[i].to);

size[x]+=size[e[i].to];

}

void dfs2(int x,int cha)

{

pos[x]=++id;bl[x]=cha;

int k=0;

for(int i=last[x];i;i=e[i].next)

if(e[i].to!=fa[x]&&size[e[i].to]>size[k])

k=e[i].to;

if(k)dfs2(k,cha);

for(int i=last[x];i;i=e[i].next)

if(e[i].to!=fa[x]&&e[i].to!=k)

dfs2(e[i].to,e[i].to);

}

int lca(int x,int y)

{

while(bl[x]!=bl[y])

if(dep[bl[x]]>dep[bl[y]])x=fa[bl[x]];

else y=fa[bl[y]];

return dep[x]<dep[y]?x:y;

}

int dis(int x,int y)

{

return d[x]+d[y]-2*d[lca(x,y)];

}

ll cal(int x,int v)

{

int t1,t2;

if(x==fa[rt])

{

t1=query(1,1,n,pos[rt],pos[rt]+size[rt]-1);

t2=tot-t1;

}

else

{

t2=query(1,1,n,pos[x],pos[x]+size[x]-1);

t1=tot-t2;

}

return ans+(ll)(t1-t2)*v;

}

void move(int x)

{

ll mn=(ll)1e60,t;

int id=0;

for(int i=last[x];i;i=e[i].next)

{

t=cal(e[i].to,e[i].v);

if(t<mn)mn=t,id=e[i].to;

}

if(mn<ans){rt=id;ans=mn;move(rt);}

}

int main()

{

n=read();m=read();

for(int i=1;i<n;i++)

{

int u=read(),v=read(),w=read();

insert(u,v,w);

}

dfs(1);

dfs2(1,1);

while(m--)

{

int u=read(),e=read();

ans+=(ll)e*dis(u,rt);

tot+=e;modify(1,1,n,pos[u],e);

move(rt);

printf("%lld\n",ans);

}

return 0;

}

« 「JoyOI」五月有奖赛暨Loi 55 Round #1 Day1 PKUSC 2014 #2 »

hzwer.com _ Home | http://hzwer.com

「BZOJ3924」[ZJOI2015] 幻想乡战略游戏

分类目录

热门文章

Myfriends

近期评论