Problem – H – Codeforces

题意：你有一个长为$n$的数组$\{x_i\}$，元素都在$[0, 2^8)$范围内。

你还有一个长为$l$的操作序列，每次操作会有两个数$a,b$，表示$x[a] = x[a] \text{or} x[b]$（按位或）。

现在给定一个数$t$，要求你在操作序列中循环执行操作（如果已经执行完了$l$个则下一次操作从第一个重新开始），总共执行$t$个操作之后，输出得到的序列。

$n,l \le 2^{18} = 262144$，$t \le 10^{18}$。

显然每一位是独立的，所以转换成$8$次只有0和1的问题即可。

我们可以转换一下思路，考虑每个位置是什么时候变成1的。

一个比较显然的想法是对一个操作$a,b$，可以连一条从$b$指向$a$的边，然后跑一遍最短路即可得知每个位置变成1的时间。

但是这样有一些问题，因为$b$之前有可能被修改过，它在同一轮中的不同时刻的值不一定相同。

所以可以把每个点拆成（被修改的次数+1）个点，第一个点是没有被修改的状态。

那么每次操作时先给$a$新建一个点，然后连边（边权是间隔的操作次数），然后从$b$的最新的结点向$a$最新的结点连边（边权也是间隔的操作次数）。

不过注意一个点变成1之后是可以等到下一轮再执行前面的操作的，所以每个点的最后一个点向第一个点补一条边变成一个环（当然要保证每个点的环长度都是$l$）。

每次只有初始距离为0的点不同，跑8次最短路即可。每个点变成1的时间自然就是它那个环的所有点中距离最小的那个。

#include <bits/stdc++.h>
 
using namespace std;
 
constexpr int maxn = 524305;
 
long long d[maxn];
bool vis[maxn];
vector<pair<int, int> > G[maxn];
 
vector<int> vec[maxn];
int u[maxn], v[maxn];
 
int a[maxn], ans[maxn];
 
void solve(int n, int m, int k, long long lim) {
	int s = n + m + 1;
	G[s].clear();
 
	for (int i = 1; i <= n; i++)
		if (a[i] >> k & 1)
			G[s].push_back(make_pair(i, 0));
	
	memset(d, 63, sizeof(d));
	memset(vis, 0, sizeof(vis));
 
	priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > heap;
 
	d[s] = 0;
	heap.push(make_pair(0, s));
 
	while (!heap.empty()) {
		int x = heap.top().second;
		heap.pop();
 
		if (vis[x])
			continue;
		
		vis[x] = true;

 
		for (auto pi : G[x]) {
			int y = pi.first, w = pi.second;
 
			if (!vis[y] && d[y] > d[x] + w) {
				d[y] = d[x] + w;

				heap.push(make_pair(d[y], y));
			}
		}
	}
 
	for (int i = 1; i <= n; i++) {
		long long tmp = d[0];
 
		for (auto x : vec[i])
			tmp = min(tmp, d[x]);
 
		if (tmp <= lim)
			ans[i] |= 1 << k;
	}
}
 
int main() {
 
	int n, m;
	long long lim;
 
	scanf("%d%d%lld", &n, &m, &lim);
 
	for (int i = 1; i <= n; i++)
		vec[i].push_back(i);
 
	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		u[i] = x;
		v[i] = y;
 
		G[vec[x].back()].push_back(make_pair(i + n, (vec[x].back() <= n ? i : i - (vec[x].back() - n))));
		G[vec[y].back()].push_back(make_pair(i + n, (vec[y].back() <= n ? i : i - (vec[y].back() - n))));
		vec[x].push_back(i + n);
	}

	for (int i = 1; i <= n; i++)
		if ((int)vec[i].size() > 1) {
			int t = vec[i].back() - n;

			G[vec[i].back()].push_back(make_pair(i, m - t));
		}
 
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
 
	for (int k = 0; k < 8; k++)
		solve(n, m, k, lim);
	
	for (int i = 1; i <= n; i++)
		printf("%d%c", ans[i], (i < n ? ' ' : '\n'));
 
	return 0;
}