結果
| 問題 | No.1266 7 Colors |
| ユーザー |
 hamamu
|
| 提出日時 | 2020-10-23 23:01:46 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 175 ms / 3,000 ms |
| コード長 | 6,881 bytes |
| コンパイル時間 | 2,221 ms |
| コンパイル使用メモリ | 209,444 KB |
| 実行使用メモリ | 30,484 KB |
| 最終ジャッジ日時 | 2023-09-28 17:33:09 |
| 合計ジャッジ時間 | 6,203 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,376 KB |
| testcase_01 | AC | 1 ms
4,376 KB |
| testcase_02 | AC | 1 ms
4,380 KB |
| testcase_03 | AC | 86 ms
9,824 KB |
| testcase_04 | AC | 155 ms
22,160 KB |
| testcase_05 | AC | 91 ms
10,372 KB |
| testcase_06 | AC | 167 ms
24,272 KB |
| testcase_07 | AC | 173 ms
27,180 KB |
| testcase_08 | AC | 167 ms
22,804 KB |
| testcase_09 | AC | 129 ms
18,412 KB |
| testcase_10 | AC | 132 ms
16,904 KB |
| testcase_11 | AC | 106 ms
12,048 KB |
| testcase_12 | AC | 114 ms
13,508 KB |
| testcase_13 | AC | 121 ms
14,952 KB |
| testcase_14 | AC | 92 ms
10,452 KB |
| testcase_15 | AC | 175 ms
27,708 KB |
| testcase_16 | AC | 112 ms
13,880 KB |
| testcase_17 | AC | 174 ms
26,556 KB |
| testcase_18 | AC | 77 ms
30,484 KB |
| testcase_19 | AC | 79 ms
27,960 KB |
| testcase_20 | AC | 79 ms
27,992 KB |
| testcase_21 | AC | 44 ms
6,072 KB |
ソースコード
#include "bits/stdc++.h"
using namespace std;
using ll=long long;
using vll=vector< ll>;
using vvll=vector< vll>;
using vvvll=vector< vvll>;
using vvvvll=vector<vvvll>;
using dd=double;
using vdd=vector< dd>;
using vvdd=vector< vdd>;
using pll=pair<ll,ll>; using tll=tuple<ll,ll,ll>; using qll=tuple<ll,ll,ll,ll>;
using vpll=vector< pll>;
constexpr ll INF = 1LL << 60;
struct Fast{ Fast(){ cin.tie(0); ios::sync_with_stdio(false); cout<<fixed<<setprecision(numeric_limits<double>::max_digits10); } } fast;
#define REPS(i, S, E) for (ll i = (S); i <= (E); i++)
#define REP(i, N) REPS(i, 0, (N)-1)
#define DEPS(i, S, E) for (ll i = (E); i >= (S); i--)
#define DEP(i, N) DEPS(i, 0, (N)-1)
#define rep(i, S, E) for (ll i = (S); i <= (E); i++)
#define dep(i, E, S) for (ll i = (E); i >= (S); i--)
#define each(e, v) for (auto&& e : v)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; }return false; }
template<class T> inline T MaxE(vector<T>&v,ll S,ll E){ T m=v[S]; rep(i,S,E)chmax(m,v[i]); return m; }
template<class T> inline T MinE(vector<T>&v,ll S,ll E){ T m=v[S]; rep(i,S,E)chmin(m,v[i]); return m; }
template<class T> inline T MaxE(vector<T> &v) { return MaxE(v,0,(ll)v.size()-1); }
template<class T> inline T MinE(vector<T> &v) { return MinE(v,0,(ll)v.size()-1); }
template<class T> inline T Sum(vector<T> &v,ll S,ll E){ T s=T(); rep(i,S,E)s+=v[i]; return s; }
template<class T> inline T Sum(vector<T> &v) { return Sum(v,0,v.size()-1); }
template<class T> inline ll sz(T &v){ return (ll)v.size(); }
inline ll CEIL(ll a,ll b){ return (a<0) ? -(-a/b) : (a+b-1)/b; }
inline ll FLOOR(ll a,ll b){ return -CEIL(-a,b); }
#if 0
#include <atcoder/all>
using namespace atcoder;
#endif
//tuple3用テンプレート
using vtll=vector< tll>;
using vvtll=vector<vtll>;
template<class T,class S,class R> inline tuple<T,S,R>& operator+=(tuple<T,S,R> &a,const tuple<T,S,R> &b){ get<0>(a)+=get<0>(b); get<1>(a)+=get<1>(b); get<2>(a)+=get<2>(b); return a; }
template<class T,class S,class R> inline tuple<T,S,R>& operator-=(tuple<T,S,R> &a,const tuple<T,S,R> &b){ get<0>(a)-=get<0>(b); get<1>(a)-=get<1>(b); get<2>(a)-=get<2>(b); return a; }
template<class T,class S,class R> inline tuple<T,S,R>& operator*=(tuple<T,S,R> &a,const tuple<T,S,R> &b){ get<0>(a)*=get<0>(b); get<1>(a)*=get<1>(b); get<2>(a)*=get<2>(b); return a; }
template<class T,class S,class R> inline tuple<T,S,R>& operator/=(tuple<T,S,R> &a,const tuple<T,S,R> &b){ get<0>(a)/=get<0>(b); get<1>(a)/=get<1>(b); get<2>(a)/=get<2>(b); return a; }
template<class T,class S,class R> inline tuple<T,S,R>& operator%=(tuple<T,S,R> &a,const tuple<T,S,R> &b){ get<0>(a)%=get<0>(b); get<1>(a)%=get<1>(b); get<2>(a)%=get<2>(b); return a; }
template<class T,class S,class R,class Q> inline tuple<T,S,R>& operator+=(tuple<T,S,R> &a,Q b){ get<0>(a)+=b; get<1>(a)+=b; get<2>(a)+=b; return a; }
template<class T,class S,class R,class Q> inline tuple<T,S,R>& operator-=(tuple<T,S,R> &a,Q b){ get<0>(a)-=b; get<1>(a)-=b; get<2>(a)-=b; return a; }
template<class T,class S,class R,class Q> inline tuple<T,S,R>& operator*=(tuple<T,S,R> &a,Q b){ get<0>(a)*=b; get<1>(a)*=b; get<2>(a)*=b; return a; }
template<class T,class S,class R,class Q> inline tuple<T,S,R>& operator/=(tuple<T,S,R> &a,Q b){ get<0>(a)/=b; get<1>(a)/=b; get<2>(a)/=b; return a; }
template<class T,class S,class R,class Q> inline tuple<T,S,R>& operator%=(tuple<T,S,R> &a,Q b){ get<0>(a)%=b; get<1>(a)%=b; get<2>(a)%=b; return a; }
template<class T,class S,class R,class Q> inline tuple<T,S,R> operator+(const tuple<T,S,R> &a,Q b){ tuple<T,S,R> c=a; return c+=b; }
template<class T,class S,class R,class Q> inline tuple<T,S,R> operator-(const tuple<T,S,R> &a,Q b){ tuple<T,S,R> c=a; return c-=b; }
template<class T,class S,class R,class Q> inline tuple<T,S,R> operator*(const tuple<T,S,R> &a,Q b){ tuple<T,S,R> c=a; return c*=b; }
template<class T,class S,class R,class Q> inline tuple<T,S,R> operator/(const tuple<T,S,R> &a,Q b){ tuple<T,S,R> c=a; return c/=b; }
template<class T,class S,class R,class Q> inline tuple<T,S,R> operator%(const tuple<T,S,R> &a,Q b){ tuple<T,S,R> c=a; return c%=b; }
template<class T,class S,class R,class Q> inline tuple<T,S,R> operator-(Q b,const tuple<T,S,R> &a){ tuple<T,S,R> c=-a; return c+=b; }
template<class T,class S,class R> inline tuple<T,S,R> operator-(const tuple<T,S,R> &a){ tuple<T,S,R> c=a; return c*=(-1); }
template<class T,class S,class R> inline ostream &operator<<(ostream &os,const tuple<T,S,R> &a){ return os << get<0>(a) << ' ' << get<1>(a) << ' ' << get<2>(a); }
vvll cinGraph(ll nodeNum,ll edgeNum,bool isDirected){//無向false、有向true
vvll to(nodeNum);
rep(i,0,edgeNum-1){
ll v,u; cin >> v >> u;
v--; u--;
to[v].push_back(u);
if (!isDirected) to[u].push_back(v);
}
return move(to);
}
class UnionFindTree{
private:
vll par,rank,size;
public:
UnionFindTree(ll num): par(num),rank(num),size(num,1){
rep(i,0,num-1) par[i] = i;
}
bool Same(ll x,ll y) { return Root(x) == Root(y); }
ll Root(ll x) { return (par[x] == x) ? x : par[x]=Root(par[x]); }
ll Size(ll x){ return size[Root(x)]; }
void Unite(ll x,ll y){
x = Root(x);
y = Root(y);
if (x == y) return;
if (rank[x] < rank[y]) par[x] = y;
else par[y] = x;
if (rank[x] == rank[y]) rank[x]++;
size[x] = size[y] = size[x] + size[y];
}
};
/*
UnionFindTree uft(N);
uft.Unite(x,y);
bool b = uft.Same(x,y);
ll num = uft.Size(x);
ll v = uft.Root(x);
*/
void solve()
{
ll M=7;
ll n,m,q; cin >> n >> m >> q;
vector<string> s(n); rep(i,0,n-1){ string s_; cin>>s_; s[i]=s_; }
vvll to = cinGraph(n,m,false);
//vector<pair<ll,ll>> uv(m);
//rep(i,0,m-1){ ll u; ll v; cin>>u>>v; uv[i]={u,v}; }
UnionFindTree uft(n*M); //M*v+c
rep(v,0,n-1){
each(u,to[v]){
if (u<v)continue;
rep(c,0,M-1){
if (s[u][c]=='1' and s[v][c]=='1'){
uft.Unite(M*v+c,M*u+c);
}
}
}
rep(c,0,M-1){
if (s[v][c]=='1' and s[v][(c+1)%M]=='1'){
uft.Unite(M*v+c,M*v+(c+1)%M);
}
}
}
vll ans;
rep(qq,0,q-1){
ll kind,v,c; cin >> kind >> v >> c; v--; c--;
if (kind==1){
s[v][c]='1';
each(u,to[v]){
if (s[u][c]=='1'){
uft.Unite(M*v+c,M*u+c);
}
}
if (s[v][(c+1)%M]=='1'){
uft.Unite(M*v+c,M*v+(c+1)%M);
}
if (s[v][(c+M-1)%M]=='1'){
uft.Unite(M*v+c,M*v+(c+M-1)%M);
}
}
else{
ans.push_back(uft.Size(M*v));
}
}
each(e,ans) cout << e << '\n';
}
int main(){
#if 1
solve();
#else
ll t; cin >> t;
rep(i, 0, t-1){
solve();
}
#endif
return 0;
}