結果
| 問題 | No.1266 7 Colors |
| ユーザー |
 hamamu
|
| 提出日時 | 2020-10-23 23:01:46 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 140 ms / 3,000 ms |
| コード長 | 6,881 bytes |
| コンパイル時間 | 2,266 ms |
| コンパイル使用メモリ | 205,420 KB |
| 最終ジャッジ日時 | 2025-01-15 13:49:56 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 19 |
ソースコード
·#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、有向truevvll 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+crep(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 1solve();#elsell t; cin >> t;rep(i, 0, t-1){solve();}#endifreturn 0;}