結果
問題 | No.1266 7 Colors |
ユーザー |
![]() |
提出日時 | 2020-10-23 22:49:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 150 ms / 3,000 ms |
コード長 | 3,418 bytes |
コンパイル時間 | 2,047 ms |
コンパイル使用メモリ | 181,700 KB |
実行使用メモリ | 14,968 KB |
最終ジャッジ日時 | 2024-07-21 11:52:16 |
合計ジャッジ時間 | 5,542 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define all(x) (x).begin(),(x).end()#define rep(i, n) for (int i = 0; i < (n); i++)#define chmin(x, y) (x) = min((x), (y))#define chmax(x, y) (x) = max((x), (y))#define endl "\n"typedef long long ll;typedef pair<int, int> pii;typedef pair<ll, ll> pll;template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {os << "["; for (const auto &v : vec) {os << v << ","; } os << "]";return os;}template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}struct UnionFind {vector<int> data;int gnum;UnionFind(int size) : data(size, -1), gnum(size) {}bool unionSet(int x, int y) {x = root(x); y = root(y);if (x != y) {if (data[y] < data[x]) swap(x, y);data[x] += data[y]; data[y] = x;gnum--;}return x != y;}bool findSet(int x, int y) {return root(x) == root(y);}int root(int x) {return data[x] < 0 ? x : data[x] = root(data[x]);}int size(int x) {return -data[root(x)];}int getGroupNum() {return gnum;}vector<vector<int>> getGroups() {int now = 0;map<int, vector<int>> G;for (int i = 0; i < data.size(); i++) {G[root(i)].push_back(i);}vector<vector<int>> ret;for(auto g : G) {ret.push_back(g.second);}return ret;}};void init(UnionFind &uf, vector<string> &S, vector<vector<int>> &G) {int N = G.size();for(int i = 0; i < 7 * N; i++) {int v = i / 7;int c = i % 7;int c_n = (c + 1) % 7;if (S[v][c] == '1' && S[v][c_n] == '1') {uf.unionSet(v * 7 + c, v * 7 + c_n);}}for (int i = 0; i < N; i++) {for (int j = 0; j < G[i].size(); j++) {for (int c = 0; c < 7; c++) {int u = i, v = G[i][j];if (S[u][c] == '1' && S[v][c] == '1') {uf.unionSet(u * 7 + c, v * 7 + c);}}}}}void solve() {int N, M, Q;cin >> N >> M >> Q;UnionFind uf(N * 7);vector<string> S(N);vector<vector<int>> G(N);for (int i = 0; i < N; i++) {cin >> S[i];}for (int i = 0; i < M; i++) {int u, v;cin >> u >> v;u--, v--;G[u].push_back(v);G[v].push_back(u);}init(uf, S, G);for (int i = 0; i < Q; i++) {int type, x, y;cin >> type >> x >> y;if (type == 1) {x--, y--;S[x][y] = '1';int c1 = (y + 1) % 7;int c2 = (y + 6) % 7;if (S[x][c1] == '1') uf.unionSet(x * 7 + y, x * 7 + c1);if (S[x][c2] == '1') uf.unionSet(x * 7 + y, x * 7 + c2);for(int j = 0; j < G[x].size(); j++) {int v = G[x][j];if (S[v][y] == '1') uf.unionSet(x * 7 + y, v * 7 + y);}} else {x--;cout << uf.size(7 * x) << endl;}}}int main() {#ifdef LOCAL_ENVcin.exceptions(ios::failbit);#endifcin.tie(0);ios::sync_with_stdio(false);cout.setf(ios::fixed);cout.precision(16);solve();}