結果
問題 | No.1266 7 Colors |
ユーザー | hanyu |
提出日時 | 2020-10-25 00:09:43 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 158 ms / 3,000 ms |
コード長 | 1,843 bytes |
コンパイル時間 | 2,507 ms |
コンパイル使用メモリ | 207,188 KB |
実行使用メモリ | 14,736 KB |
最終ジャッジ日時 | 2023-09-28 21:29:24 |
合計ジャッジ時間 | 6,560 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 82 ms
5,680 KB |
testcase_04 | AC | 141 ms
10,988 KB |
testcase_05 | AC | 88 ms
6,248 KB |
testcase_06 | AC | 135 ms
11,988 KB |
testcase_07 | AC | 158 ms
13,092 KB |
testcase_08 | AC | 131 ms
11,220 KB |
testcase_09 | AC | 117 ms
9,396 KB |
testcase_10 | AC | 109 ms
8,872 KB |
testcase_11 | AC | 93 ms
6,752 KB |
testcase_12 | AC | 100 ms
7,596 KB |
testcase_13 | AC | 103 ms
8,024 KB |
testcase_14 | AC | 86 ms
5,964 KB |
testcase_15 | AC | 150 ms
13,516 KB |
testcase_16 | AC | 101 ms
7,576 KB |
testcase_17 | AC | 147 ms
12,800 KB |
testcase_18 | AC | 73 ms
14,736 KB |
testcase_19 | AC | 75 ms
14,320 KB |
testcase_20 | AC | 74 ms
14,372 KB |
testcase_21 | AC | 40 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; // Union-Find Tree struct UnionFind { vector<int> par; // 親のid(親の場合, 集合の頂点数の-1倍) UnionFind(int n): par(n, -1) {} void init(int n) { par.assign(n, -1); } int find(int x) { if (par[x] < 0) return x; return par[x] = find(par[x]); } bool unite(int x, int y) { x = find(x); y = find(y); if (x == y) return false; if (par[x] > par[y]) swap(x, y); par[x] += par[y]; par[y] = x; return true; } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return -par[find(x)]; } }; int main() { cin.tie(0); ios::sync_with_stdio(false); int n, m, q; cin >> n >> m >> q; vector<string> s(n); for (int i = 0; i < n; i++) cin >> s[i]; vector<vector<int>> G(n); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; u--; v--; G[u].emplace_back(v); G[v].emplace_back(u); } UnionFind uf(7 * n); for (int i = 0; i < n; i++) { for (int j = 0; j < 7; j++) { if (s[i][j] == '1' && s[i][(j + 1) % 7] == '1') uf.unite(i + n * j, i + (n * (j + 1)) % (7 * n)); } } for (int i = 0; i < n; i++) { for (int j : G[i]) { for (int k = 0; k < 7; k++) { if (s[i][k] == '1' && s[j][k] == '1') uf.unite(i + n * k, j + n * k); } } } while (q--) { int tmp, x, y; cin >> tmp >> x >> y; x--; y--; if (tmp == 1) { s[x][y] = '1'; if (s[x][(y - 1 + 7) % 7] == '1') uf.unite(x + n * y, x + (n * ((y - 1 + 7) % 7))); if (s[x][(y + 1) % 7] == '1') uf.unite(x + n * y, x + (n * ((y + 1) % 7))); for (auto j : G[x]) { if (s[j][y] == '1') uf.unite(x + n * y, j + n * y); } } else { cout << uf.size(x) << '\n'; } } }