結果
| 問題 | No.1023 Cyclic Tour |
| ユーザー |
 LayCurse
|
| 提出日時 | 2020-04-10 22:50:58 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,104 bytes |
| コンパイル時間 | 2,605 ms |
| コンパイル使用メモリ | 218,512 KB |
| 最終ジャッジ日時 | 2025-01-09 16:33:19 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 36 TLE * 13 |
ソースコード
#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;}}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(const char c[]){int i=0;for(i=0;c[i]!='\0';i++){my_putchar_unlocked(c[i]);}}template<class S> inline void arrInsert(const int k, int &sz, S a[], const S aval){int i;sz++;for(i=sz-1;i>k;i--){a[i] = a[i-1];}a[k] = aval;}template<class S, class T> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval){int i;sz++;for(i=sz-1;i>k;i--){a[i] = a[i-1];}for(i=sz-1;i>k;i--){b[i] = b[i-1];}a[k] = aval;b[k] = bval;}template<class S, class T, class U> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval){int i;sz++;for(i=sz-1;i>k;i--){a[i] = a[i-1];}for(i=sz-1;i>k;i--){b[i] = b[i-1];}for(i=sz-1;i>k;i--){c[i] = c[i-1];}a[k] = aval;b[k] = bval;c[k] = cval;}template<class S, class T, class U, class V> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const Ucval, V d[], const V dval){int i;sz++;for(i=sz-1;i>k;i--){a[i] = a[i-1];}for(i=sz-1;i>k;i--){b[i] = b[i-1];}for(i=sz-1;i>k;i--){c[i] = c[i-1];}for(i=sz-1;i>k;i--){d[i] = d[i-1];}a[k] = aval;b[k] = bval;c[k] = cval;d[k] = dval;}struct graph{int N;int *es;int **edge;void setDirectEdge(int N__, int M, int A[], int B[], void **mem = &wmem){int i;N = N__;walloc1d(&es, N, mem);walloc1d(&edge, N, mem);walloc1d(&edge[0], M, mem);for(i=(0);i<(N);i++){es[i] = 0;}for(i=(0);i<(M);i++){es[A[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];}}};int N;int M;int A[400000];int B[400000];int C[400000];graph g;int vis[100000];int solve(int n, int b = -1){int Lj4PdHRW;vis[n] = 2;for(Lj4PdHRW=(0);Lj4PdHRW<(g.es[n]);Lj4PdHRW++){auto &i = g.edge[n][Lj4PdHRW];if(i==b){continue;}if(vis[i]==2){return 1;}if(solve(i, n)){return 1;}}vis[n] = 1;return 0;}int main(){int i;wmem = memarr;set<pair<int,int>> s0;set<pair<int,int>> s1;rd(N);rd(M);{int e98WHCEY;for(e98WHCEY=(0);e98WHCEY<(M);e98WHCEY++){rd(A[e98WHCEY]);A[e98WHCEY] += (-1);rd(B[e98WHCEY]);B[e98WHCEY] += (-1);rd(C[e98WHCEY]);C[e98WHCEY] += (-1);}}for(i=(0);i<(M);i++){if(C[i]==0){s0.insert( make_pair(A[i], B[i]) );if(s1.count(make_pair(A[i], B[i]))){wt_L("Yes");wt_L('\n');return 0;}if(s1.count(make_pair(B[i], A[i]))){wt_L("Yes");wt_L('\n');return 0;}}else{s1.insert( make_pair(A[i], B[i]) );if(s0.count(make_pair(A[i], B[i]))){wt_L("Yes");wt_L('\n');return 0;}if(s0.count(make_pair(B[i], A[i]))){wt_L("Yes");wt_L('\n');return 0;}if(s1.count(make_pair(B[i], A[i]))){wt_L("Yes");wt_L('\n');return 0;}}}int WYIGIcGE = M;for(i=(0);i<(WYIGIcGE);i++){if(C[i]==0){arrInsert(M,M,A,B[i],B,A[i]);}}g.setDirectEdge(N,M,A,B);for(i=(0);i<(N);i++){if(!vis[i]){if(solve(i)){wt_L("Yes");wt_L('\n');return 0;}}}wt_L("No");wt_L('\n');return 0;}// cLay varsion 20200408-1// --- original code ---// int N, M, A[4d5], B[4d5], C[4d5];// graph g;//// int vis[1d5];// int solve(int n, int b = -1){// vis[n] = 2;// rep[g.edge[n]](i,g.es[n]){// if(i==b) continue;// if(vis[i]==2) return 1;// if(solve(i, n)) return 1;// }// vis[n] = 1;// return 0;// }//// {// set<pair<int,int>> s0, s1;// rd(N,M,(A--,B--,C--)(M));//// rep(i,M){// if(C[i]==0){// s0.insert( make_pair(A[i], B[i]) );// if(s1.count(make_pair(A[i], B[i]))) wt("Yes"), return 0;// if(s1.count(make_pair(B[i], A[i]))) wt("Yes"), return 0;// } else {// s1.insert( make_pair(A[i], B[i]) );// if(s0.count(make_pair(A[i], B[i]))) wt("Yes"), return 0;// if(s0.count(make_pair(B[i], A[i]))) wt("Yes"), return 0;// if(s1.count(make_pair(B[i], A[i]))) wt("Yes"), return 0;// }// }//// REP(i,M) if(C[i]==0) arrInsert(M,M,A,B[i],B,A[i]);// g.setDirectEdge(N,M,A,B);// rep(i,N) if(!vis[i]) if(solve(i)) wt("Yes"), return 0;// wt("No");// }