結果
| 問題 | No.1605 Matrix Shape |
| ユーザー |
 LayCurse
|
| 提出日時 | 2021-07-16 22:03:28 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 62 ms / 2,000 ms |
| コード長 | 6,657 bytes |
| コンパイル時間 | 3,001 ms |
| コンパイル使用メモリ | 225,572 KB |
| 最終ジャッジ日時 | 2025-01-23 01:56:09 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 34 |
ソースコード
#pragma GCC optimize("Ofast")#pragma GCC optimize("unroll-loops")#pragma GCC optimize("inline")#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);}template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){walloc1d(arr, x2-x1, mem);(*arr) -= x1;}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;}}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');}}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;}inline int comp(int res[], void *mem = wmem){int i;int sz=0;int*cnt;walloc1d(&cnt, N, &mem);for(i=(0);i<(N);i++){cnt[i] = 0;}for(i=(0);i<(N);i++){cnt[get(i)] = 1;}for(i=(0);i<(N);i++){if(cnt[i]){cnt[i] = sz++;}}for(i=(0);i<(N);i++){res[i] = cnt[get(i)];}return sz;}};template<class T> int coordcomp_L(int n, T arr[], int res[] = NULL, void *mem = wmem){int i;int k = 0;pair<T,int>*r;walloc1d(&r, n, &mem);for(i=(0);i<(n);i++){r[i].first = arr[i];r[i].second = i;}sort(r, r+n);if(res != NULL){for(i=(0);i<(n);i++){if(i && r[i].first != r[i-1].first){k++;}res[r[i].second] = k;}}else{for(i=(0);i<(n);i++){if(i && r[i].first != r[i-1].first){k++;}arr[r[i].second] = k;}}return k+1;}template<class T> int coordcomp_L(int n1, T arr1[], int n2, T arr2[], int res1[] = NULL, int res2[] = NULL, void *mem = wmem){int i;int k = 0;pair<T,int>*r;walloc1d(&r, n1+n2, &mem);for(i=(0);i<(n1);i++){r[i].first = arr1[i];r[i].second = i;}for(i=(0);i<(n2);i++){r[n1+i].first = arr2[i];r[n1+i].second = n1+i;}sort(r, r+n1+n2);for(i=(0);i<(n1+n2);i++){if(i && r[i].first != r[i-1].first){k++;}if(r[i].second < n1){if(res1!=NULL){res1[r[i].second] = k;}else{arr1[r[i].second] = k;}}else{if(res2!=NULL){res2[r[i].second-n1] = k;}else{arr2[r[i].second-n1] = k;}}}return k+1;}int N;int A[200000];int B[200000];unionFind uf;int sz;int chk;int deg[200000];int main(){int i;wmem = memarr;rd(N);{int Lj4PdHRW;for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){rd(A[Lj4PdHRW]);rd(B[Lj4PdHRW]);}}sz =coordcomp_L(N,A,N,B);uf.walloc(sz,1);for(i=(0);i<(N);i++){chk += uf(A[i], B[i]);}if(chk != sz-1){wt_L(0);wt_L('\n');return 0;}for(i=(0);i<(N);i++){deg[A[i]]++;deg[B[i]]--;}int xr20shxY;remove_reference<decltype(abs(deg[xr20shxY]))>::type WYIGIcGE;int t_ynMSdg = 0;if((0) > ((sz)-1)){WYIGIcGE = 0;}else{for(xr20shxY = 0; xr20shxY <= (sz)-1; xr20shxY++){if(t_ynMSdg == 0){WYIGIcGE = abs(deg[xr20shxY]);t_ynMSdg = 1;continue;}WYIGIcGE += abs(deg[xr20shxY]);}if(t_ynMSdg==0){WYIGIcGE = 0;}}chk =WYIGIcGE;if(chk==0){wt_L(sz);wt_L('\n');}else if(chk==2){wt_L(1);wt_L('\n');}else{wt_L(0);wt_L('\n');}return 0;}// cLay version 20210708-1// --- original code ---// int N, A[2d5], B[];// unionFind uf;// int sz, chk, deg[];// {// rd(N,(A,B)(N));// sz = coordcomp(N,A,N,B);// uf.walloc(sz,1);// rep(i,N) chk += uf(A[i], B[i]);// if(chk != sz-1) wt(0), return 0;// rep(i,N) deg[A[i]]++, deg[B[i]]--;// chk = sum[i,0,sz](abs(deg[i]));// wt(if[chk==0, sz, chk==2, 1, 0]);// }