結果
問題 | No.1266 7 Colors |
ユーザー |
![]() |
提出日時 | 2020-12-24 18:57:13 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 127 ms / 3,000 ms |
コード長 | 5,047 bytes |
コンパイル時間 | 2,268 ms |
コンパイル使用メモリ | 202,660 KB |
最終ジャッジ日時 | 2025-01-17 06:42:17 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
//#include <tourist>#include <bits/stdc++.h>//#include <atcoder/all>using namespace std;//using namespace atcoder;typedef long long ll;typedef long double ld;typedef unsigned int uint;typedef unsigned long long ull;typedef pair<ll, ll> p;const int INF = 1e9;const double eps = 1e-7;const ll LINF = ll(1e18);const int MOD = 1000000007;const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};const long double pi = 4 * atan(1);#define yes cout << "Yes" << endl#define YES cout << "YES" << endl#define no cout << "No" << endl#define NO cout << "NO" << endl#define rep(i, n) for (int i = 0; i < n; i++)#define ALL(v) v.begin(), v.end()#define debug(v) \cout << #v << ":"; \for (auto x : v) \{ \cout << x << ' '; \} \cout << endl;template <class T>bool chmax(T &a, const T &b){if (a < b){a = b;return 1;}return 0;}template <class T>bool chmin(T &a, const T &b){if (b < a){a = b;return 1;}return 0;}template <typename T>istream &operator>>(istream &is, vector<T> &v){for (T &x : v)is >> x;return is;}//cout<<fixed<<setprecision(15);有効数字15桁//-std=c++14//g++ yarudake.cpp -std=c++17 -I .ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }// 素集合データ構造struct UnionFind{// par[i]:データiが属する木の親の番号。i == par[i]のとき、データiは木の根ノードであるvector<int> par;// sizes[i]:根ノードiの木に含まれるデータの数。iが根ノードでない場合は無意味な値となるvector<int> sizes;UnionFind(int n) : par(n), sizes(n, 1){// 最初は全てのデータiがグループiに存在するものとして初期化rep(i, n) par[i] = i;}// データxが属する木の根を得るint find(int x){if (x == par[x])return x;return par[x] = find(par[x]); // 根を張り替えながら再帰的に根ノードを探す}// 2つのデータx, yが属する木をマージするvoid unite(int x, int y){// データの根ノードを得るx = find(x);y = find(y);// 既に同じ木に属しているならマージしないif (x == y)return;// xの木がyの木より大きくなるようにするif (sizes[x] < sizes[y])swap(x, y);// xがyの親になるように連結するpar[y] = x;sizes[x] += sizes[y];// sizes[y] = 0; // sizes[y]は無意味な値となるので0を入れておいてもよい}// 2つのデータx, yが属する木が同じならtrueを返すbool same(int x, int y){return find(x) == find(y);}// データxが含まれる木の大きさを返すint size(int x){return sizes[find(x)];}};int main(){cin.tie(0);ios::sync_with_stdio(false);ll n, m, q;cin >> n >> m >> q;vector<string> s(n);rep(i, n) cin >> s[i];UnionFind uf(7 * n);vector<vector<ll>> e(n);rep(i, n){rep(j, 6){if (s[i][j] == '1' && s[i][j + 1] == '1'){uf.unite(i + j * n, i + (j + 1) * n);}}if (s[i][0] == '1' && s[i][6] == '1'){uf.unite(i + 0 * n, i + 6 * n);}}rep(i, m){int u, v;cin >> u >> v;u--;v--;rep(j, 7){if (s[u][j] == '1' && s[v][j] == '1'){uf.unite(u + j * n, v + j * n);}}e[u].push_back(v);e[v].push_back(u);}vector<ll> ans;rep(i, q){int flag, x, y;cin >> flag >> x >> y;x--;y--;if (flag == 1){if (y == 0){if (s[x][6] == '1')uf.unite(x, x + 6 * n);}else{if (s[x][y - 1] == '1')uf.unite(x + y * n, x + (y - 1) * n);}if (y == 6){if (s[x][0] == '1')uf.unite(x, x + 6 * n);}else{if (s[x][y + 1] == '1')uf.unite(x + y * n, x + (y + 1) * n);}rep(j, e[x].size()){if (s[e[x][j]][y] == '1'){uf.unite(x + y * n, e[x][j] + y * n);}}s[x][y] = '1';}else{ans.push_back(uf.size(x));}}rep(i, ans.size()) cout << ans[i] << "\n";}