首页 > 其他分享 >[PA2024] Modernizacja Bajtocji 题解

[PA2024] Modernizacja Bajtocji 题解

时间:2024-11-04 10:09:21浏览次数:4  
标签:cnt Bajtocji int 题解 电脑 Byteasar PA2024 居民 op

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

相关文章

  • SP30785 ADAAPPLE - Ada and Apple 题解
    洛谷题目传送门博客园可能食用更佳题目大意:给定一棵权值为000或11......
  • P11244 吻秋 题解
    洛谷题目传送门博客园可能食用更佳题目大意:给你mmm个长度为nn......
  • P11244 吻秋 题解
    洛谷题目传送门博客园可能食用更佳题目大意:给你\(m\)个长度为\(n\)的序列\(a\),\(Q\)次操作:1xy将\(a_x\)与\(a_y\)的所有元素取出至长度为\(2n\)的序列\(b\),将\(b\)升序重排后\(a_x\getsb_{1\dotsn},a_y\getsb_{n+1\dots2n}\);2ij询问\(a_{......
  • 2024秋季赛部分题解(A,E,F,I,J)
    J 螺旋塔思路:一眼签到题直接写#include<iostream>#include<map>#include<vector>#include<stack>#include<queue>#include<cmath>#include<algorithm>#include<cstring>#include<string>#include<set>usingname......
  • P11229 [CSP-J 2024] 小木棍 题解
    算法一,dp首先对于\(10^5\)的数据,很明显,如果用longlong是绝对会爆炸的,所以使用string类型进行dp.定义状态\(f_i\),表示用\(i\)根木棍能拼出的最小数字.显然,可以先初始化1~7的情况.状态转移:\(f_i=cmp(f_i,f_{i-stk_j}+j).\),其中,cmp为比较函数,j为0~9......