結果
| 問題 | No.1266 7 Colors |
| ユーザー |
 uchiiii
|
| 提出日時 | 2020-10-24 01:33:15 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 175 ms / 3,000 ms |
| コード長 | 5,983 bytes |
| コンパイル時間 | 3,572 ms |
| コンパイル使用メモリ | 227,428 KB |
| 実行使用メモリ | 17,504 KB |
| 最終ジャッジ日時 | 2023-09-28 19:57:35 |
| 合計ジャッジ時間 | 7,578 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,380 KB |
| testcase_01 | AC | 1 ms
4,376 KB |
| testcase_02 | AC | 1 ms
4,380 KB |
| testcase_03 | AC | 80 ms
5,956 KB |
| testcase_04 | AC | 152 ms
13,072 KB |
| testcase_05 | AC | 87 ms
6,480 KB |
| testcase_06 | AC | 153 ms
14,064 KB |
| testcase_07 | AC | 171 ms
15,644 KB |
| testcase_08 | AC | 157 ms
13,416 KB |
| testcase_09 | AC | 138 ms
11,128 KB |
| testcase_10 | AC | 122 ms
10,176 KB |
| testcase_11 | AC | 98 ms
7,544 KB |
| testcase_12 | AC | 105 ms
8,348 KB |
| testcase_13 | AC | 116 ms
9,184 KB |
| testcase_14 | AC | 86 ms
6,540 KB |
| testcase_15 | AC | 175 ms
15,928 KB |
| testcase_16 | AC | 105 ms
8,600 KB |
| testcase_17 | AC | 165 ms
15,200 KB |
| testcase_18 | AC | 70 ms
17,504 KB |
| testcase_19 | AC | 70 ms
17,172 KB |
| testcase_20 | AC | 71 ms
17,184 KB |
| testcase_21 | AC | 42 ms
4,376 KB |
ソースコード
#pragma GCC target("avx2")
#pragma GCC optimize("03")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std; using ld = long double; using ll = long long;
using ull = unsigned long long;
#define endl "\n"
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define ALL(x) (x).begin(), (x).end()
#define QUERY int num_query;cin>>num_query; while(num_query--)
// int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1};
constexpr int INF=1<<30;
constexpr ll LINF=1LL<<60;
constexpr ll mod=1e9+7;
void flush() {cout<<flush;}
template <typename T> static constexpr T inf = numeric_limits<T>::max()/2;
template<class T>vector<T> vec(int len, T elem) { return vector<T>(len, elem); } // auto dp = vec(52, vec(103, vec(103, INF)));
template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
template<class T>inline int popcount(T a) {return __builtin_popcountll(a);}
template<class T>inline T emod(T a, T p) { return (a%p + p) % p;}
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << '(' << pa.first << ',' << pa.second << ')'; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {os << '\n'; for (auto v : vec) os << v << ' '; os << '\n'; return os;}
template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
struct MyIO {
MyIO(){
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(15);
}
} IO_OI;
#ifdef LOCAL
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << H;
debug_out(T...);
}
#define debug(...) \
cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif
//-------------------
class UnionFind {
private:
unsigned size_; std::vector<int> par, rank; //par = root? -size: par
public:
UnionFind() : size_(0), par(std::vector<int>()), rank(std::vector<int>()) {};
UnionFind(unsigned size__) : size_(size__) {
par.resize(size_+1); rank.resize(size_+1);
for (unsigned i = 0; i <= size_; i++) par[i] = -1, rank[i] = 0;
}
//unsigned size() { return size_; }
unsigned root(unsigned x) {return par[x] < 0 ? x : par[x] = root(par[x]); }
bool same(unsigned x, unsigned y) { return root(x) == root(y); }
void unite(unsigned x, unsigned y) {
x = root(x), y = root(y);
if (x == y) return;
if (rank[x] < rank[y])par[y] += par[x], par[x] = y;
else if (rank[x] == rank[y])par[x] += par[y], par[y] = x, rank[x]++;
else par[x] += par[y], par[y] = x;
}
int size(int x){ return -par[root(x)];}
bool operator==(const UnionFind &u) { return par == u.par; }
bool operator!=(const UnionFind &u) { return par != u.par; }
};
int main() {
int n,m,q;cin>>n>>m>>q;
vector<string> ss(n);
UnionFind uf(7*n);
rep(i,n) {
cin>>ss[i];
rep(j,7) {
if(ss[i][j]=='1' and ss[i][(j+1)%7]=='1') {
uf.unite(i*7+j, i*7+emod(j+1, 7));
}
}
}
vector<vector<int>> G(n);
rep(i,m) {
int u,v;cin>>u>>v;u--;v--;
G[u].push_back(v);
G[v].push_back(u);
rep(j,7) {
if(ss[u][j]=='1' and ss[v][j]=='1') {
uf.unite(u*7+j, v*7+j);
}
}
// rep(j,7) {
// if(ss[u][j]=='1' and ss[v][(j+1)%7]=='1') {
// uf.unite(u*7+j, v*7+emod(j+1, 7));
// }
// }
// rep(j,7) {
// if(ss[v][j]=='1' and ss[u][(j+1)%7]=='1') {
// uf.unite(v*7+j, u*7+emod(j+1, 7));
// }
// }
}
while(q--) {
int qq,u,j;cin>>qq>>u>>j; u--; j--;
if(qq==1) {
ss[u][j] = '1';
if(ss[u][emod(j+1, 7)]=='1') uf.unite(7*u+j, 7*u+emod(j+1, 7));
if(ss[u][emod(j-1, 7)]=='1') uf.unite(7*u+j, 7*u+emod(j-1, 7));
for(auto v: G[u]) {
if(ss[u][j]=='1' and ss[v][j]=='1') {
uf.unite(u*7+j, v*7+j);
}
// if(ss[u][j]=='1' and ss[v][(j+1)%7]=='1') {
// uf.unite(u*7+j, v*7+emod(j+1, 7));
// }
// if(ss[v][j]=='1' and ss[u][(j+1)%7]=='1') {
// uf.unite(v*7+j, u*7+emod(j+1, 7));
// }
}
} else {
cout << uf.size(u*7) << endl;
}
}
}