BZOJ1095: [ZJOI2007]Hide 捉迷藏

2018-02-28 0 Comments 1,757 Views 0 Times

Time Limit: 40 Sec Memory Limit: 256 MB

Description

　　捉迷藏 Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩
捉迷藏游戏。他们的家很大且构造很奇特，由N个屋子和N-1条双向走廊组成，这N-1条走廊的分布使得任意两个屋
子都互相可达。游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这N个屋子的灯。在起初的
时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要
求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，Jiajia希望知道可能的最远的两
个孩子的距离（即最远的两个关灯房间的距离）。我们将以如下形式定义每一种操作： C(hange) i 改变第i个房
间的照明状态，若原来打开，则关闭；若原来关闭，则打开。 G(ame) 开始一次游戏，查询最远的两个关灯房间的
距离。

Input

　　第一行包含一个整数N，表示房间的个数，房间将被编号为1,2,3…N的整数。接下来N-1行每行两个整数a, b，
表示房间a与房间b之间有一条走廊相连。接下来一行包含一个整数Q，表示操作次数。接着Q行，每行一个操作，如
上文所示。

Output

　　对于每一个操作Game，输出一个非负整数到hide.out，表示最远的两个关灯房间的距离。若只有一个房间是关
着灯的，输出0；若所有房间的灯都开着，输出-1。

Sample Input

8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
7
G
C 1
G
C 2
G
C 1
G

Sample Output

4
3
3
4

HINT

对于100%的数据， N ≤100000, M ≤500000。

Solution

注意：在函数中传递struct时，如果struct内含一个堆之类的，必须要加&，传地址！！！否则会复制一份，非常慢！！！

这题是我的第一道动态点分治。

写起来有点复杂，但思路还是比较清晰。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
const int N=400100;
int n,tot,Q,Time,Next[N],head[N],tree[N],ST[N][35],First[N],dep[N],Log[N],size[N],fa[N],NOW[N];
int MAX=0;
bool visit[N];
struct PQ
{
	priority_queue<int>heap,DelMark;
	void Insert(int x) { heap.push(x);}
	void Erase(int x) { DelMark.push(x);}
	void UPD()
	{
		while (DelMark.size()&&heap.top()==DelMark.top())
			heap.pop(),DelMark.pop();
	}
	void Pop() { UPD();heap.pop();}
	int Top() { UPD();return heap.top();}
	int se_Top()
	{ 
		int x=Top();
		Pop();
		int ans=Top();
		Insert(x);
		return ans;
	}
	int SIZE() { return heap.size()-DelMark.size();}
}Q1[N],Q2[N],Ans;
void add(int x,int y)
{
	tot++;
	Next[tot]=head[x];
	head[x]=tot;
	tree[tot]=y;
}
void pre_lca(int u,int father)
{
	ST[++Time][0]=dep[u]=dep[father]+1;
	First[u]=Time;
	for (int i=head[u];i;i=Next[i])
	if (tree[i]!=father)
	{
		pre_lca(tree[i],u);
		ST[++Time][0]=dep[u];
	}
}
void pre_ST()
{
	Log[1]=0;
	for (int i=2;i<=Time;i++) Log[i]=Log[i>>1]+1;
	for (int i=1;i<=Log[Time];i++)
		for (int j=1;j<=Time;j++) ST[j][i]=min(ST[j+(1<<(i-1))][i-1],ST[j][i-1]);
}
void Get_Size(int u,int father)
{
	size[u]=1;
	for (int i=head[u];i;i=Next[i])
	{
		int v=tree[i];
		if (v==father||visit[v]) continue;
		Get_Size(v,u);
		size[u]+=size[v];
	}
}
int Get_CG(int u,int father,int MaxSize)
{
	for (int i=head[u];i;i=Next[i])
	{
		int v=tree[i];
		if (visit[v]||v==father) continue;
		if (size[v]+size[v]>MaxSize) return Get_CG(v,u,MaxSize);
	}
	return u;
}
void UPD_Ans(PQ &s,int opt)
{
	if (opt==1)
	{
		if (s.SIZE()>=2) Ans.Insert(s.Top()+s.se_Top());
	}else
	{
		if (s.SIZE()>=2) Ans.Erase(s.Top()+s.se_Top());
	}
}
void DFS(int u,int father,PQ &s,int depth)
{
	s.Insert(depth);
	for (int i=head[u];i;i=Next[i])
	{
		int v=tree[i];
		if (v==father||visit[v]) continue;
		DFS(v,u,s,depth+1);
	}
}
int TDC(int u)
{
	Get_Size(u,0);
	int t=Get_CG(u,0,size[u]);
	visit[t]=1;
	Q2[t].Insert(0);
	for (int i=head[t];i;i=Next[i])
	{
		int v=tree[i];
		if (visit[v]) continue;
		PQ pq;
		DFS(v,t,pq,1);
		int CG=TDC(v);
		Q1[CG]=pq;Q2[t].Insert(Q1[CG].Top());
		fa[CG]=t;
	}
	UPD_Ans(Q2[t],1);
	return t;
}
int Calc_ST(int u,int v)
{
	u=First[u];v=First[v];
	if (u>v) swap(u,v);
	int len=Log[v-u+1];
	return min(ST[u][len],ST[v-(1<<len)+1][len]);
}
int Get_dis(int u,int v)
{
	return dep[u]+dep[v]-Calc_ST(u,v)*2;
}
void change(int u,int last)
{
	UPD_Ans(Q2[u],2);
	if (last) Q2[u].Insert(0);
		else Q2[u].Erase(0); 
	UPD_Ans(Q2[u],1);
	for (int i=u;fa[i];i=fa[i])
	{
		UPD_Ans(Q2[fa[i]],2);
		if (Q1[i].SIZE()) 
		Q2[fa[i]].Erase(Q1[i].Top());
		int dis=Get_dis(u,fa[i]);
		if (last) Q1[i].Insert(dis);
			else Q1[i].Erase(dis);
		if (Q1[i].SIZE()) 
			Q2[fa[i]].Insert(Q1[i].Top());
		UPD_Ans(Q2[fa[i]],1);
	}
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n-1;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	pre_lca(1,0);
	pre_ST();
	TDC(1);
	scanf("%d",&Q);
	int Off=n;
	while (Q--)
	{
		char s[2];int x;
		scanf("%s",s);
		if (s[0]=='G')
		{
			if (Off<=1) printf("%d\n",Off-1);
				else printf("%d\n",Ans.Top());
		}else
		{
			scanf("%d",&x);
			change(x,NOW[x]);
			if (NOW[x]==1) Off++;else Off--;
			NOW[x]^=1;
		}
	}
	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

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<queue>

using namespace std;

const int N=400100;

int n,tot,Q,Time,Next[N],head[N],tree[N],ST[N][35],First[N],dep[N],Log[N],size[N],fa[N],NOW[N];

int MAX=0;

bool visit[N];

struct PQ

{

priority_queue<int>heap,DelMark;

void Insert(int x) { heap.push(x);}

void Erase(int x) { DelMark.push(x);}

void UPD()

{

while (DelMark.size()&&heap.top()==DelMark.top())

heap.pop(),DelMark.pop();

}

void Pop() { UPD();heap.pop();}

int Top() { UPD();return heap.top();}

int se_Top()

{

int x=Top();

Pop();

int ans=Top();

Insert(x);

return ans;

}

int SIZE() { return heap.size()-DelMark.size();}

}Q1[N],Q2[N],Ans;

void add(int x,int y)

{

tot++;

Next[tot]=head[x];

head[x]=tot;

tree[tot]=y;

}

void pre_lca(int u,int father)

{

ST[++Time][0]=dep[u]=dep[father]+1;

First[u]=Time;

for (int i=head[u];i;i=Next[i])

if (tree[i]!=father)

{

pre_lca(tree[i],u);

ST[++Time][0]=dep[u];

}

void pre_ST()

{

Log[1]=0;

for (int i=2;i<=Time;i++) Log[i]=Log[i>>1]+1;

for (int i=1;i<=Log[Time];i++)

for (int j=1;j<=Time;j++) ST[j][i]=min(ST[j+(1<<(i-1))][i-1],ST[j][i-1]);

}

void Get_Size(int u,int father)

{

size[u]=1;

for (int i=head[u];i;i=Next[i])

{

int v=tree[i];

if (v==father||visit[v]) continue;

Get_Size(v,u);

size[u]+=size[v];

}

int Get_CG(int u,int father,int MaxSize)

{

for (int i=head[u];i;i=Next[i])

{

int v=tree[i];

if (visit[v]||v==father) continue;

if (size[v]+size[v]>MaxSize) return Get_CG(v,u,MaxSize);

}

return u;

}

void UPD_Ans(PQ &s,int opt)

{

if (opt==1)

{

if (s.SIZE()>=2) Ans.Insert(s.Top()+s.se_Top());

}else

{

if (s.SIZE()>=2) Ans.Erase(s.Top()+s.se_Top());

}

void DFS(int u,int father,PQ &s,int depth)

{

s.Insert(depth);

for (int i=head[u];i;i=Next[i])

{

int v=tree[i];

if (v==father||visit[v]) continue;

DFS(v,u,s,depth+1);

}

int TDC(int u)

{

Get_Size(u,0);

int t=Get_CG(u,0,size[u]);

visit[t]=1;

Q2[t].Insert(0);

for (int i=head[t];i;i=Next[i])

{

int v=tree[i];

if (visit[v]) continue;

PQ pq;

DFS(v,t,pq,1);

int CG=TDC(v);

Q1[CG]=pq;Q2[t].Insert(Q1[CG].Top());

fa[CG]=t;

}

UPD_Ans(Q2[t],1);

return t;

}

int Calc_ST(int u,int v)

{

u=First[u];v=First[v];

if (u>v) swap(u,v);

int len=Log[v-u+1];

return min(ST[u][len],ST[v-(1<<len)+1][len]);

}

int Get_dis(int u,int v)

{

return dep[u]+dep[v]-Calc_ST(u,v)*2;

}

void change(int u,int last)

{

UPD_Ans(Q2[u],2);

if (last) Q2[u].Insert(0);

else Q2[u].Erase(0);

UPD_Ans(Q2[u],1);

for (int i=u;fa[i];i=fa[i])

{

UPD_Ans(Q2[fa[i]],2);

if (Q1[i].SIZE())

Q2[fa[i]].Erase(Q1[i].Top());

int dis=Get_dis(u,fa[i]);

if (last) Q1[i].Insert(dis);

else Q1[i].Erase(dis);

if (Q1[i].SIZE())

Q2[fa[i]].Insert(Q1[i].Top());

UPD_Ans(Q2[fa[i]],1);

}

int main()

{

scanf("%d",&n);

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

{

int x,y;

scanf("%d%d",&x,&y);

add(x,y);add(y,x);

}

pre_lca(1,0);

pre_ST();

TDC(1);

scanf("%d",&Q);

int Off=n;

while (Q--)

{

char s[2];int x;

scanf("%s",s);

if (s[0]=='G')

{

if (Off<=1) printf("%d\n",Off-1);

else printf("%d\n",Ans.Top());

}else

{

scanf("%d",&x);

change(x,NOW[x]);

if (NOW[x]==1) Off++;else Off--;

NOW[x]^=1;

}

return 0;

}

He Kai's blog

BZOJ1095: [ZJOI2007]Hide 捉迷藏

Description

Input

Output

Sample Input

Sample Output

HINT

Solution

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可

发表评论取消回复

Description

Input

Output

Sample Input

Sample Output

HINT

Solution

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可

发表评论 取消回复

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可

发表评论取消回复