abcdeffa's Blog

当局者迷，旁观者清。

0%

GMOJ S5466 【玩游戏】

发表于

Description

给你一个有 $n$ 个点 $m$ 条边的无向图，定义两点间一条路径的权值为所经边的边权最大值，再定义两点间的最短路的长度为两点间所有路径的权值的最小值。现在有 $Q$ 次操作，为加边或求给定的 $k$ 个点对之间的最短路的长度异或和是否为 0。

保证加边操作的次数不超过 5000。

Solution

一道极其无聊的强行二合一题。

为什么题目要问“给定的 $k$ 个点对之间的最短路的长度异或和是否为 0”呢？

其实原题面在这里强行插入了一个 Nim 游戏，我觉得这样做太无聊了于是就在简述题意时把这个要求改掉了。

然后考虑一下怎么求两点间的最短路。

考虑建出最小生成树，然后倍增求一发两点间简单路径上的边权的最大值即可。

为什么这个是对的？证明类似于 NOIP 的货车运输那题。

感兴趣的可以自己去看，在这里就不赘述了。

Code

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
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
#pragma GCC optimize (2)
#pragma GCC optimize (3)
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("inline")
#pragma GCC optimize ("-fgcse")
#pragma GCC optimize ("-fgcse-lm")
#pragma GCC optimize ("-fipa-sra")
#pragma GCC optimize ("-ftree-pre")
#pragma GCC optimize ("-ftree-vrp")
#pragma GCC optimize ("-fpeephole2")
#pragma GCC optimize ("-ffast-math")
#pragma GCC optimize ("-fsched-spec")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("-falign-jumps")
#pragma GCC optimize ("-falign-loops")
#pragma GCC optimize ("-falign-labels")
#pragma GCC optimize ("-fdevirtualize")
#pragma GCC optimize ("-fcaller-saves")
#pragma GCC optimize ("-fcrossjumping")
#pragma GCC optimize ("-fthread-jumps")
#pragma GCC optimize ("-funroll-loops")
#pragma GCC optimize ("-fwhole-program")
#pragma GCC optimize ("-freorder-blocks")
#pragma GCC optimize ("-fschedule-insns")
#pragma GCC optimize ("inline-functions")
#pragma GCC optimize ("-ftree-tail-merge")
#pragma GCC optimize ("-fschedule-insns2")
#pragma GCC optimize ("-fstrict-aliasing")
#pragma GCC optimize ("-fstrict-overflow")
#pragma GCC optimize ("-falign-functions")
#pragma GCC optimize ("-fcse-skip-blocks")
#pragma GCC optimize ("-fcse-follow-jumps")
#pragma GCC optimize ("-fsched-interblock")
#pragma GCC optimize ("-fpartial-inlining")
#pragma GCC optimize ("no-stack-protector")
#pragma GCC optimize ("-freorder-functions")
#pragma GCC optimize ("-findirect-inlining")
#pragma GCC optimize ("-fhoist-adjacent-loads")
#pragma GCC optimize ("-frerun-cse-after-loop")
#pragma GCC optimize ("inline-small-functions")
#pragma GCC optimize ("-finline-small-functions")
#pragma GCC optimize ("-ftree-switch-conversion")
#pragma GCC optimize ("-foptimize-sibling-calls")
#pragma GCC optimize ("-fexpensive-optimizations")
#pragma GCC optimize ("-funsafe-loop-optimizations")
#pragma GCC optimize ("inline-functions-called-once")
#pragma GCC optimize ("-fdelete-null-pointer-checks")
#pragma GCC optimize (2)
#include <cstdio>
#include <iostream>
#include <algorithm>
#define maxN 200010
using namespace std;
struct Edge{ long long x, y, c, g; } a[maxN << 1], b[maxN << 1], p[maxN << 1];
long long len = 0, n = 0, m = 0, K = 0;;
char st[11];
long long f[maxN][20], w[maxN][20];
long long dep[maxN], F[maxN], h[maxN];
long long read ()
{
	long long x = 0;
	char c = getchar();
	while(c < '0' || c > '9')
	{
		c = getchar();
	}
	while(c >= '0' && c <= '9')
	{
		x = x * 10 + (c - '0');
		c = getchar();
	}
	return x;
}
bool cmp (Edge A, Edge B)
{
	return A.c < B.c;
}
long long max (long long x, long long y)
{
	return x > y ? x : y;
}
long long find (long long x)
{
	if(x == F[x])
	{
		return x;
	}
	else
	{
		return F[x] = find(F[x]);
	}
}
void ins (long long x, long long y, long long c)
{
	len++;
	p[len].x = x;
	p[len].y = y;
	p[len].c = c;
	p[len].g = h[x];
	h[x] = len;
}
void pre ()
{
	sort(a + 1, a + m + 1, cmp);
	for(long long i = 1;i <= n; i++)
	{
		F[i] = i;
	}
	long long now = 0;
	for(long long i = 1;i <= m; i++)
	{
		long long x = a[i].x, y = a[i].y;
		long long tx = find(x), ty = find(y);
		if(tx != ty)
		{
			F[tx] = ty;
			b[++now] = a[i];
		}
	}
	m = n - 1;
}
void work ()
{
	len = 0;
	sort(b + 1, b + m + 1, cmp);
	for(long long i = 1;i <= n; i++)
	{
		h[i] = 0;
		F[i] = i;
		dep[i] = 0;
	}
	for(long long i = 1;i <= m; i++)
	{
		long long x = b[i].x, y = b[i].y, c = b[i].c;
		long long tx = find(x), ty = find(y);
		if(tx != ty)
		{
			F[tx] = ty;
			ins(x, y, c), ins(y, x, c);
		}
	}
}
void dfs (long long x)
{
	for(long long i = h[x];i;i = p[i].g)
	{
		long long y = p[i].y;
		if(!dep[y])
		{
			dep[y] = dep[x] + 1;
			f[y][0] = x;
			w[y][0] = p[i].c;
			dfs(y);
		}
	}
}
long long calc (long long x, long long y)
{
	long long res = 0;
	if(dep[x] < dep[y])
	{
		long long t = x;
		x = y;
		y = t;
	}
	for(long long i = 19;i >= 0; i--)
	{
		if(dep[f[x][i]] >= dep[y])
		{
			res = max(res, w[x][i]);
			x = f[x][i];
		}
	}
	if(x == y)
	{
		return res;
	}
	for(long long i = 19;i >= 0; i--)
	{
		if(f[x][i] != f[y][i])
		{
			res = max(res, max(w[x][i], w[y][i]));
			x = f[x][i];
			y = f[y][i];
		}
	}
	return max(res, max(w[x][0], w[y][0]));
}
int main ()
{
	n = read();
	m = read();
	K = read();
	for(long long i = 1;i <= m; i++)
	{
		a[i].x = read();
		a[i].y = read();
		a[i].c = read();
	}
	pre();
	for(long long i = 1;i <= m; i++)
	{
		long long x = b[i].x, y = b[i].y, c = b[i].c;
		ins(x, y, c), ins(y, x, c);
	}
	long long root = 1;
	dep[root] = 1;
	dfs(root);
	for(long long j = 1;j <= 19; j++)
	{
		for(long long i = 1;i <= n; i++)
		{
			f[i][j] = f[f[i][j - 1]][j - 1];
			w[i][j] = max(w[i][j - 1], w[f[i][j - 1]][j - 1]);
		}
	}
	long long Q = 0;
	scanf("%lld", &Q);
	while(Q--)
	{
		scanf("%s", st + 1);
		if(st[1] == 'g')
		{
			long long Ans = 0;
			for(long long i = 1;i <= K; i++)
			{
				long long x = 0, y = 0;
				x = read();
				y = read();
				Ans ^= calc(x, y);
			}
			printf("%s\n", Ans ? "madoka" : "Baozika");
		}
		else
		{
			m++;
			b[m].x = read();
			b[m].y = read();
			b[m].c = read();
			work();
			long long root = 1;
			dep[root] = 1;
			dfs(root);
			for(long long j = 1;j <= 19; j++)
			{
				for(long long i = 1;i <= n; i++)
				{
					f[i][j] = f[f[i][j - 1]][j - 1];
					w[i][j] = max(w[i][j - 1], w[f[i][j - 1]][j - 1]);
				}
			}
		}
	}
	return 0;
}