結果
問題 | No.1266 7 Colors |
ユーザー | 👑 Nachia |
提出日時 | 2020-10-23 22:51:15 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 349 ms / 3,000 ms |
コード長 | 1,544 bytes |
コンパイル時間 | 1,759 ms |
コンパイル使用メモリ | 172,024 KB |
実行使用メモリ | 16,228 KB |
最終ジャッジ日時 | 2023-09-28 17:19:05 |
合計ジャッジ時間 | 8,836 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
5,728 KB |
testcase_01 | AC | 3 ms
5,844 KB |
testcase_02 | AC | 4 ms
5,832 KB |
testcase_03 | AC | 248 ms
8,072 KB |
testcase_04 | AC | 329 ms
11,980 KB |
testcase_05 | AC | 258 ms
8,072 KB |
testcase_06 | AC | 339 ms
12,844 KB |
testcase_07 | AC | 349 ms
13,676 KB |
testcase_08 | AC | 328 ms
12,300 KB |
testcase_09 | AC | 309 ms
10,808 KB |
testcase_10 | AC | 309 ms
10,192 KB |
testcase_11 | AC | 266 ms
8,604 KB |
testcase_12 | AC | 274 ms
9,196 KB |
testcase_13 | AC | 293 ms
9,784 KB |
testcase_14 | AC | 256 ms
8,196 KB |
testcase_15 | AC | 345 ms
13,884 KB |
testcase_16 | AC | 285 ms
9,460 KB |
testcase_17 | AC | 341 ms
13,236 KB |
testcase_18 | AC | 277 ms
16,228 KB |
testcase_19 | AC | 171 ms
15,792 KB |
testcase_20 | AC | 173 ms
15,616 KB |
testcase_21 | AC | 221 ms
6,816 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using LL = long long; using ULL = unsigned long long; #define rep(i,n) for(int i=0; i<(n); i++) struct dsu { vector<int> V; vector<int> Z; dsu(int n) { V.resize(n); Z.assign(n, 1); rep(i, n) V[i] = i; } int root(int a) { if (V[a] == a) return a; return V[a] = root(V[a]); } void unite(int u, int v) { u = root(u); v = root(v); if (u == v) return; V[u] = v; Z[v] += Z[u]; } int size(int a) { return Z[root(a)]; } }; int N, M, Q; bool X[100000][7]; vector<int> E[100000]; int main() { cin >> N >> M >> Q; dsu G(N * 7); rep(i, N) rep(x, 7) { char c; cin >> c; X[i][x] = (c == '1'); } rep(i, N) rep(x, 7) { if (X[i][x]) if (X[i][(x + 1) % 7]) G.unite(i * 7 + x, i * 7 + (x + 1) % 7); } rep(i, M) { int u, v; cin >> u >> v; u--; v--; rep(x, 7) if (X[u][x]) if (X[v][x]) G.unite(u * 7 + x, v * 7 + x); E[u].push_back(v); E[v].push_back(u); } rep(q,Q){ int c; cin >> c; if (c == 1) { int x, y; cin >> x >> y; x--; y--; X[x][y] = true; if (X[x][(y + 1) % 7]) G.unite(x * 7 + y, x * 7 + (y + 1) % 7); if (X[x][(y + 6) % 7]) G.unite(x * 7 + y, x * 7 + (y + 6) % 7); for (int e : E[x]) { if (X[e][y]) G.unite(x * 7 + y, e * 7 + y); } } if (c == 2) { int x, z; cin >> x >> z; x--; cout << G.size(x * 7) << endl; } } return 0; }