社区讨论
数据过水还是我的代码正确?
P3733[HAOI2017] 八纵八横参与者 3已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @mhjhvl0k
- 此快照首次捕获于
- 2025/11/04 02:49 4 个月前
- 此快照最后确认于
- 2025/11/04 02:49 4 个月前
请注意看我代码中的 函数,我没有判重边的情况,即
CPPif (v != fa) ,但是我的代码却过了??#include <bits/stdc++.h>
const int N = 505;
const int K = 1005;
typedef std::bitset<K> bit;
int n, m, q, tot, vis[N], pos[K], flag[K]; bit dis[N];
std::string s;
std::vector<std::pair<int, bit>> e[N];
bit base[K]; int t[K];
struct Que { int a, b, t; bit w; } que[K];
void insert(int tim, bit x) {
for (int i = 1000; i >= 0; --i) {
if (!x[i]) continue;
if (!base[i].any()) { t[i] = tim; base[i] = x; return; }
if (tim > t[i]) std::swap(tim, t[i]), std::swap(base[i], x);
x ^= base[i];
}
}
int stk[K], top;
void ask(int tim) {
bit x; x.reset();
for (int i = 1000; i >= 0; --i) {
if (tim > t[i]) continue;
if (!x[i]) x ^= base[i];
}
for (int i = 0; x.any(); ++i)
stk[top++] = x[i], x[i] = 0;
for (int i = top - 1; ~i; --i)
std::cout << stk[i]; std::cout << std::endl;
top = 0;
}
void dfs(int u, int fa) {
vis[u] = 1;
for (auto [v, w] : e[u])
if (v != fa)
if (vis[v]) insert(1e9, dis[u] ^ dis[v] ^ w);
else dis[v] = dis[u] ^ w, dfs(v, u);
}
int main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cin >> n >> m >> q;
for (int i = 1, u, v; i <= m; ++i) {
std::cin >> u >> v >> s; bit w(s);
e[u].emplace_back(v, w), e[v].emplace_back(u, w);
}
dfs(1, 0);
for (int i = 1; i <= q; ++i) {
std::cin >> s; int a, b;
if (s[1] == 'd') {
std::cin >> a >> b >> s; bit bi(s);
pos[++tot] = i; flag[i] = 1;
que[i] = {a, b, (int)1e9, bi};
} else if (s[1] == 'h') {
std::cin >> a >> s; bit bi(s);
que[pos[a]].t = i - 1;
que[i] = {que[pos[a]].a, que[pos[a]].b, (int)1e9, bi};
pos[a] = i; flag[i] = 1;
} else {
std::cin >> a;
que[pos[a]].t = i - 1;
}
}
for (int i = 0; i <= q; ++i) {
if (flag[i]) insert(que[i].t, dis[que[i].a] ^ dis[que[i].b] ^ que[i].w);
ask(i);
}
return 0;
}
回复
共 7 条回复,欢迎继续交流。
正在加载回复...