結果
問題 | No.1266 7 Colors |
ユーザー | LayCurse |
提出日時 | 2020-10-24 18:26:01 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 53 ms / 3,000 ms |
コード長 | 8,634 bytes |
コンパイル時間 | 2,942 ms |
コンパイル使用メモリ | 217,572 KB |
実行使用メモリ | 12,672 KB |
最終ジャッジ日時 | 2024-07-21 15:23:36 |
合計ジャッジ時間 | 5,004 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 3 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 32 ms
7,168 KB |
testcase_04 | AC | 46 ms
10,112 KB |
testcase_05 | AC | 32 ms
7,552 KB |
testcase_06 | AC | 51 ms
10,624 KB |
testcase_07 | AC | 53 ms
11,392 KB |
testcase_08 | AC | 49 ms
10,240 KB |
testcase_09 | AC | 43 ms
9,088 KB |
testcase_10 | AC | 41 ms
8,960 KB |
testcase_11 | AC | 36 ms
7,936 KB |
testcase_12 | AC | 38 ms
8,192 KB |
testcase_13 | AC | 39 ms
8,576 KB |
testcase_14 | AC | 34 ms
7,296 KB |
testcase_15 | AC | 53 ms
11,392 KB |
testcase_16 | AC | 38 ms
8,320 KB |
testcase_17 | AC | 51 ms
11,264 KB |
testcase_18 | AC | 22 ms
12,672 KB |
testcase_19 | AC | 23 ms
11,648 KB |
testcase_20 | AC | 23 ms
11,776 KB |
testcase_21 | AC | 11 ms
6,528 KB |
ソースコード
#pragma GCC optimize ("Ofast") #include<bits/stdc++.h> using namespace std; void*wmem; char memarr[96000000]; template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){ static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] ); (*arr)=(T*)(*mem); (*mem)=((*arr)+x); } inline int my_getchar_unlocked(){ static char buf[1048576]; static int s = 1048576; static int e = 1048576; if(s == e && e == 1048576){ e = fread_unlocked(buf, 1, 1048576, stdin); s = 0; } if(s == e){ return EOF; } return buf[s++]; } inline void rd(int &x){ int k; int m=0; x=0; for(;;){ k = my_getchar_unlocked(); if(k=='-'){ m=1; break; } if('0'<=k&&k<='9'){ x=k-'0'; break; } } for(;;){ k = my_getchar_unlocked(); if(k<'0'||k>'9'){ break; } x=x*10+k-'0'; } if(m){ x=-x; } } inline void rd(char &c){ int i; for(;;){ i = my_getchar_unlocked(); if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){ break; } } c = i; } inline int rd(char c[]){ int i; int sz = 0; for(;;){ i = my_getchar_unlocked(); if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){ break; } } c[sz++] = i; for(;;){ i = my_getchar_unlocked(); if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){ break; } c[sz++] = i; } c[sz]='\0'; return sz; } struct MY_WRITER{ char buf[1048576]; int s; int e; MY_WRITER(){ s = 0; e = 1048576; } ~MY_WRITER(){ if(s){ fwrite_unlocked(buf, 1, s, stdout); } } } ; MY_WRITER MY_WRITER_VAR; void my_putchar_unlocked(int a){ if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){ fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout); MY_WRITER_VAR.s = 0; } MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a; } inline void wt_L(char a){ my_putchar_unlocked(a); } inline void wt_L(int x){ int s=0; int m=0; char f[10]; if(x<0){ m=1; x=-x; } while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } if(m){ my_putchar_unlocked('-'); } while(s--){ my_putchar_unlocked(f[s]+'0'); } } inline void wt_L(unsigned x){ int s=0; char f[10]; while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } while(s--){ my_putchar_unlocked(f[s]+'0'); } } inline void wt_L(long long x){ int s=0; int m=0; char f[20]; if(x<0){ m=1; x=-x; } while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } if(m){ my_putchar_unlocked('-'); } while(s--){ my_putchar_unlocked(f[s]+'0'); } } inline void wt_L(unsigned long long x){ int s=0; char f[21]; while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } while(s--){ my_putchar_unlocked(f[s]+'0'); } } int WRITER_DOUBLE_DIGIT = 15; inline int writerDigit_double(){ return WRITER_DOUBLE_DIGIT; } inline void writerDigit_double(int d){ WRITER_DOUBLE_DIGIT = d; } inline void wt_L(double x){ const int d = WRITER_DOUBLE_DIGIT; int k; int r; double v; if(x!=x || (x==x+1 && x==2*x)){ my_putchar_unlocked('E'); my_putchar_unlocked('r'); my_putchar_unlocked('r'); return; } if(x < 0){ my_putchar_unlocked('-'); x = -x; } x += 0.5 * pow(0.1, d); r = 0; v = 1; while(x >= 10*v){ v *= 10; r++; } while(r >= 0){ r--; k = floor(x / v); if(k >= 10){ k = 9; } if(k <= -1){ k = 0; } x -= k * v; v *= 0.1; my_putchar_unlocked(k + '0'); } if(d > 0){ my_putchar_unlocked('.'); v = 1; for(r=(0);r<(d);r++){ v *= 0.1; k = floor(x / v); if(k >= 10){ k = 9; } if(k <= -1){ k = 0; } x -= k * v; my_putchar_unlocked(k + '0'); } } } inline void wt_L(const char c[]){ int i=0; for(i=0;c[i]!='\0';i++){ my_putchar_unlocked(c[i]); } } inline void wt_L(string &x){ int i=0; for(i=0;x[i]!='\0';i++){ my_putchar_unlocked(x[i]); } } template<class S, class T> inline S moddw_L(S a, const T b){ a %= b; if(a < 0){ a += b; } return a; } struct unionFind{ int*d; int N; int M; inline void malloc(const int n){ d = (int*)std::malloc(n*sizeof(int)); M = n; } inline void malloc(const int n, const int fg){ d = (int*)std::malloc(n*sizeof(int)); M = n; if(fg){ init(n); } } inline void free(void){ std::free(d); } inline void walloc(const int n, void **mem=&wmem){ walloc1d(&d, n, mem); M = n; } inline void walloc(const int n, const int fg, void **mem=&wmem){ walloc1d(&d, n, mem); M = n; if(fg){ init(n); } } inline void init(const int n){ int i; N = n; for(i=(0);i<(n);i++){ d[i] = -1; } } inline void init(void){ init(M); } inline int get(int a){ int t = a; int k; while(d[t]>=0){ t=d[t]; } while(d[a]>=0){ k=d[a]; d[a]=t; a=k; } return a; } inline int connect(int a, int b){ if(d[a]>=0){ a=get(a); } if(d[b]>=0){ b=get(b); } if(a==b){ return 0; } if(d[a] < d[b]){ d[a] += d[b]; d[b] = a; } else{ d[b] += d[a]; d[a] = b; } return 1; } inline int operator()(int a){ return get(a); } inline int operator()(int a, int b){ return connect(a,b); } inline int& operator[](const int a){ return d[a]; } inline int size(int a){ a = get(a); return -d[a]; } inline int sizeList(int res[]){ int i; int sz=0; for(i=(0);i<(N);i++){ if(d[i]<0){ res[sz++] = -d[i]; } } return sz; } } ; struct graph{ int N; int*es; int**edge; void setEdge(int N__, int M, int A[], int B[], void **mem = &wmem){ int i; N = N__; walloc1d(&es, N, mem); walloc1d(&edge, N, mem); for(i=(0);i<(N);i++){ es[i] = 0; } for(i=(0);i<(M);i++){ es[A[i]]++; es[B[i]]++; } for(i=(0);i<(N);i++){ walloc1d(&edge[i], es[i], mem); } for(i=(0);i<(N);i++){ es[i] = 0; } for(i=(0);i<(M);i++){ edge[A[i]][es[A[i]]++] = B[i]; edge[B[i]][es[B[i]]++] = A[i]; } } } ; int N; int M; int Q; int A[100000]; int B[100000]; int T; int X; int Y; graph g; char S[100000][9]; int main(){ int hCmBdyQB, i; wmem = memarr; int x; int y; unionFind uf; rd(N); rd(M); rd(Q); { int Lj4PdHRW; for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){ rd(S[Lj4PdHRW]); } } { int e98WHCEY; for(e98WHCEY=(0);e98WHCEY<(M);e98WHCEY++){ rd(A[e98WHCEY]);A[e98WHCEY] += (-1); rd(B[e98WHCEY]);B[e98WHCEY] += (-1); } } g.setEdge(N,M,A,B); uf.walloc(N*7, 1); for(i=(0);i<(N);i++){ int j; for(j=(0);j<(7);j++){ if(S[i][j]==S[i][(j+1)%7] && S[i][(j+1)%7]=='1'){ uf(i*7+j, i*7+(j+1)%7); } } } for(i=(0);i<(M);i++){ int j; for(j=(0);j<(7);j++){ if(S[A[i]][j]==S[B[i]][j] && S[B[i]][j]=='1'){ uf(A[i]*7+j, B[i]*7+j); } } } for(hCmBdyQB=(0);hCmBdyQB<(Q);hCmBdyQB++){ rd(T); rd(X);X += (-1); rd(Y);Y += (-1); if(T==1){ int YREPHmFM; S[X][Y] = '1'; if(S[X][Y]==S[X][(moddw_L((Y+1),7))] && S[X][(moddw_L((Y+1),7))]=='1'){ uf(X*7+Y, X*7+(moddw_L((Y+1),7))); } if(S[X][Y]==S[X][(moddw_L((Y-1),7))] && S[X][(moddw_L((Y-1),7))]=='1'){ uf(X*7+Y, X*7+(moddw_L((Y-1),7))); } for(YREPHmFM=(0);YREPHmFM<(g.es[X]);YREPHmFM++){ auto &i = g.edge[X][YREPHmFM]; if(S[X][Y]==S[i][Y] && S[i][Y]=='1'){ uf(X*7+Y, i*7+Y); } } } else{ wt_L(uf.size(X*7)); wt_L('\n'); } } return 0; } // cLay varsion 20201018-2 // --- original code --- // int N, M, Q, A[1d5], B[1d5], T, X, Y; // graph g; // char S[1d5][9]; // { // int x, y; // unionFind uf; // rd(N,M,Q,S(N),(A--,B--)(M)); // g.setEdge(N,M,A,B); // uf.walloc(N*7, 1); // rep(i,N) rep(j,7) if(S[i][j]==S[i][(j+1)%7]=='1') uf(i*7+j, i*7+(j+1)%7); // rep(i,M) rep(j,7) if(S[A[i]][j]==S[B[i]][j]=='1') uf(A[i]*7+j, B[i]*7+j); // // rep(Q){ // rd(T, X--, Y--); // if(T==1){ // S[X][Y] = '1'; // if(S[X][Y]==S[X][(Y+1)%%7]=='1') uf(X*7+Y, X*7+(Y+1)%%7); // if(S[X][Y]==S[X][(Y-1)%%7]=='1') uf(X*7+Y, X*7+(Y-1)%%7); // rep[g.edge[X]](i,g.es[X]) if(S[X][Y]==S[i][Y]=='1') uf(X*7+Y, i*7+Y); // } else { // wt(uf.size(X*7)); // } // } // }