「重庆联考2017D1T3」玩游戏 - 重构稀疏表/LCT | Bill Yang's Blog

「重庆联考2017D1T3」玩游戏 - 重构稀疏表/LCT

题目大意

题目描述

    小A得了忧郁综合症,小B正在想办法开导她。
    机智的小B决定陪着小A玩游戏,他从魔法的世界里变出一张无向联通图,每条边上都有边权。小B定义一条路径的权值为所有经过边中的最大权值,小A则定义两点的最短路径为所有路径中权值最小的路径权。
    每次小A先选出两个点$m_1,m_2$,然后小B选出两个点$b_1,b_2$,计算出它们的最短路径$m,b$,然后小B会拿出两堆灵魂宝石,一堆有$m$个,另一堆有$b$个。然后小A先从一堆中选出若干个灵魂宝石拿走,接下来小B重复同样的操作,如此反复,直到取走最后一颗灵魂宝石,然后取走最后一颗宝石的人获胜。
    小B认为这样游戏太简单,于是他会不定期向这张图上加上一些边,以增大游戏难度。
    小A具有预知未来的能力,她看到了自己和小B在未来游戏中的选择,以及小B增加的边。现在对于每次游戏,小A想知道自己是否存在必胜的方法。但是预知未来已经消耗了她太多精力,出于疲惫她只好找到了你。

输入格式

    第一行两个数$N$和$M$,表示这张无向图初始的点数与边数;
    接下来$M$行,每行三个数$u,v,q$,表示点$u$和点$v$之间存在一条权值为$q$的边;
    接下来一行一个数$Q$,表示操作总数;
    接下来$Q$行,表示操作,每行格式为下面两条中的一条:
    $1.add\,u\,v\,q$:表示在$u$与$v$之间加上一条边权为$q$的边;
    $2.game\,m_1\,m_2\,b_1\,b_2$:表示一次游戏,其中小A的选择点$m_1,m_2$,小B的选择点$b_1,b_2$。
    数据保证$1\le u,v,m_1,m_2,b_1,b_2\le n,1\le q\,\,m1\neq m2$且$b_1\neq b_2$

输出格式

    对于每个game输出一行,若小A存在必胜策略,则输出madoka,否则输出Baozika,以回车结尾。

数据范围


题目分析

看完数据范围就知道这道题是来搞笑的了(为了NOIP缩减范围)。

经分析,若题目中$m=b$,则后手有必胜策略,因为他可以和先手作出一模一样的选法。若$m\neq b$,则先手有必胜策略,因为他可以将石子数变为相等,转化为第一种情况。

因此本题任务转化为求瓶颈路。

方法一:暴力重构稀疏表

求瓶颈路有经典的最小生成树做法。
先求出最小生成树,然后用稀疏表预处理最小生成树上的$2^k$祖先,优化查询路径最大值。

每次询问直接用$lca$查询路径最大。

因为$add$操作$\le1000$,因此我们每次加边的时候若更新最小生成树权值,可以放心大胆重构整棵最小生成树。
从根结点重新向下遍历,每个结点重新处理$2^k$祖先。

方法二:直接上LCT

不用多说了吧,数据范围$add\le10^5$依然能过。


代码

LCT代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
LL max(LL a,LL b) {
if(a>b)return a;
return b;
}
const int maxn=5005,maxm=100005;
struct Tree {
int father,child[2];
bool rev;
int maxl;
LL max,val;
};
struct Link_Cut_Tree {
Tree tree[maxn+maxm+5000];
stack<int>S;
#define ls(x) tree[x].child[0]
#define rs(x) tree[x].child[1]
#define fa(x) tree[x].father
#define rev(x) tree[x].rev
bool isroot(int index) {
return ls(fa(index))!=index&&rs(fa(index))!=index;
}
bool checkson(int index) {
return rs(fa(index))==index;
}
void push_down(int index) {
if(!rev(index))return;
swap(ls(index),rs(index));
rev(ls(index))^=1;
rev(rs(index))^=1;
rev(index)=0;
}
void push_up(int index) {
tree[index].max=max(max(tree[ls(index)].max,tree[rs(index)].max),tree[index].val);
if(tree[index].max!=tree[index].val) {
if(tree[ls(index)].max>tree[rs(index)].max)tree[index].maxl=tree[ls(index)].maxl;
else tree[index].maxl=tree[rs(index)].maxl;
} else tree[index].maxl=index;
}
void rotate(int index) {
int father=fa(index),grand=fa(father),side=checkson(index);
if(!isroot(father))tree[grand].child[checkson(father)]=index;
tree[father].child[side]=tree[index].child[side^1];
fa(tree[father].child[side])=father;
fa(father)=index;
tree[index].child[side^1]=father;
fa(index)=grand;
push_up(father);
push_up(index);
}
void splay(int index) {
S.push(index);
for(int i=index; !isroot(i); i=fa(i))S.push(fa(i));
while(!S.empty())push_down(S.top()),S.pop();
for(int father; !isroot(index); rotate(index)) {
father=fa(index);
if(!isroot(father))rotate(checkson(index)==checkson(father)?father:index);
}
}
void access(int index) {
for(int son=0; index; son=index,index=fa(index)) {
splay(index);
rs(index)=son;
push_up(index);
}
}
void reverse(int index) {
access(index);
splay(index);
rev(index)^=1;
}
void link(int x,int y) { //private
reverse(x);
fa(x)=y;
}
void split(int x,int y) {
reverse(x);
access(y);
splay(y);
}
void cut(int x,int y) {
split(x,y);
ls(y)=fa(x)=0;
}
void link(int index,int x,int y,LL val) { //index:num for edge
link(x,index);
link(index,y);
tree[index].val=tree[index].max=val;
tree[index].maxl=index;
}
void cutedge(int x,int y) {
if(x>y)swap(x,y);
split(y,x);
int edge=fa(y);
cut(y,edge);
cut(edge,x);
}
int get_root(int index) {
access(index);
splay(index);
int u=index;
while(ls(u))u=ls(u);
return u;
}
} lct;
int n,m,q,L[maxm+5000],R[maxm+5000],cnt=0;
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int();
LL v=Get_Int();
if(lct.get_root(x)==lct.get_root(y)) {
lct.split(x,y);
if(lct.tree[y].max>v) {
lct.cutedge(L[lct.tree[y].maxl-n],R[lct.tree[y].maxl-n]);
lct.link(n+i,x,y,v);
}
} else lct.link(n+i,x,y,v);
L[i]=x;
R[i]=y;
}
q=Get_Int();
for(int i=1; i<=q; i++) {
char opt=' ';
while(opt!='g'&&opt!='a')opt=getchar();
if(opt=='g') {
int x=Get_Int(),y=Get_Int(),x2=Get_Int(),y2=Get_Int();
lct.split(x,y);
LL v1=lct.tree[y].max;
lct.split(x2,y2);
LL v2=lct.tree[y2].max;
if(v1!=v2)puts("madoka");
else puts("Baozika");
} else {
int x=Get_Int(),y=Get_Int();
LL v=Get_Int();
L[++cnt+m]=x;
R[cnt+m]=y;
if(lct.get_root(x)==lct.get_root(y)) {
lct.split(x,y);
if(lct.tree[y].max>v) {
lct.cutedge(L[lct.tree[y].maxl-n],R[lct.tree[y].maxl-n]);
lct.link(n+m+cnt,x,y,v);
}
} else lct.link(n+m+cnt,x,y,v);
}
}
return 0;
}

本篇文章有用吗?有用还不快点击!
0%