Description
Byteland 正在走向现代化。最新的政府项目旨在为那些没有电脑的村镇居民提供电脑。Byteasar 正在监督该计划中的一个村庄——Bytetown——的现代化进程,目前那里没有一个居民拥有电脑。
Bytetown 有 \(n\) 个居民,为了简单起见,Byteasar 将他们用 \(1\) 到 \(n\) 的整数编号。最初没有一个居民拥有电脑。Byteasar 的任务是处理三种形式的事件:
- \(\texttt{+}\ a_i\ b_i\):将一台电脑送给 Bytetown 的居民。然而,Byteasar 并不知道电脑是送给了编号为 \(a_i\) 还是 \(b_i\) 的居民。可能会出现 \(a_i = b_i\) 的情况——在这种情况下,电脑肯定送给了编号为 \(a_i\) 的居民。可以确定的是,电脑被送到了目前还没有电脑的居民手中。
- \(\texttt{-}\ c_i\):编号为 \(c_i\) 的居民的电脑坏了。可以肯定的是,该居民曾经拥有一台电脑(但现在不再拥有,因此将来可能会收到一台新电脑)。
- \(\texttt{?}\ d_i\):Byteasar 需要(利用迄今为止获得的所有信息)确定编号为 \(d_i\) 的居民:肯定有电脑,肯定没有电脑,还是不确定他是否有电脑。
请编写一个程序,帮助 Byteasar 回答所提出的问题!
注:在居民的电脑坏掉的前一刻,Byteasar 不一定可以确定这个居民是否有电脑。换句话说,在某居民电脑坏掉之前,不一定可以从之前的事件中确定他是否有电脑。
Solution
首先没有 \(-\) 操作是好做的,如果把 \(+\) 操作的两个居民连一条边,则一定会连成树/基环树。对于一个连通块,如果大小为 \(1\),则一定没电脑,否则如果为树,则全部无法确定,基环树则每个人都有。
加上 \(-\) 操作后就把操作的点从其所在连通块删掉,原连通块如果为基环树则还是,否则如果删掉后只有一个点就看成单点,否则还是个树。
但是暴力删是做不了的,考虑把删点看成加点,即删掉点 \(a\) 时,只将原连通块的状态更新但不删点,然后新建一个点 \(a'\) 并把 \(a\) 放到 \(a'\) 上。
时间复杂度:\(O((n+q)\log n)\)。
Code
#include <bits/stdc++.h>
// #define int int64_t
const int kMaxN = 1.3e6 + 5;
const char kC[] = "0?1";
int n, q, cnt;
int id[kMaxN], fa[kMaxN], sz[kMaxN], op[kMaxN];
// 0 : 单点,1 : 树,2 : 基环树
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void unionn(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) op[fx] = 2;
else fa[fx] = fy, op[fy] = ((op[fx] == 2 || op[fy] == 2) ? 2 : 1), sz[fy] += sz[fx];
}
void dickdreamer() {
std::cin >> n >> q;
cnt = n;
for (int i = 1; i <= n; ++i) id[i] = fa[i] = i, sz[i] = 1;
for (int i = 1; i <= q; ++i) {
std::string s;
int a, b;
std::cin >> s;
if (s[0] == '+') {
std::cin >> a >> b;
unionn(id[a], id[b]);
} else if (s[0] == '-') {
std::cin >> a;
int f = find(id[a]);
if (op[f] == 1 && --sz[f] == 1) op[f] = 0;
id[a] = ++cnt;
fa[cnt] = cnt, sz[cnt] = 1;
} else {
std::cin >> a;
std::cout << kC[op[find(id[a])]];
}
}
}
int32_t main() {
#ifdef ORZXKR
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
int T = 1;
// std::cin >> T;
while (T--) dickdreamer();
// std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
return 0;
}
标签:cnt,Bajtocji,int,题解,电脑,Byteasar,PA2024,居民,op
From: https://www.cnblogs.com/Scarab/p/18524587