結果
問題 | No.1283 Extra Fee |
ユーザー | LayCurse |
提出日時 | 2020-11-15 09:40:04 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 179 ms / 2,000 ms |
コード長 | 10,821 bytes |
コンパイル時間 | 2,822 ms |
コンパイル使用メモリ | 216,668 KB |
実行使用メモリ | 80,256 KB |
最終ジャッジ日時 | 2024-11-16 07:13:03 |
合計ジャッジ時間 | 6,382 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
13,772 KB |
testcase_01 | AC | 3 ms
11,720 KB |
testcase_02 | AC | 3 ms
11,848 KB |
testcase_03 | AC | 3 ms
11,724 KB |
testcase_04 | AC | 4 ms
11,728 KB |
testcase_05 | AC | 3 ms
11,724 KB |
testcase_06 | AC | 4 ms
11,852 KB |
testcase_07 | AC | 3 ms
11,720 KB |
testcase_08 | AC | 3 ms
11,856 KB |
testcase_09 | AC | 4 ms
13,768 KB |
testcase_10 | AC | 3 ms
11,724 KB |
testcase_11 | AC | 10 ms
18,348 KB |
testcase_12 | AC | 13 ms
20,412 KB |
testcase_13 | AC | 9 ms
16,408 KB |
testcase_14 | AC | 30 ms
27,076 KB |
testcase_15 | AC | 47 ms
33,508 KB |
testcase_16 | AC | 11 ms
8,448 KB |
testcase_17 | AC | 133 ms
73,216 KB |
testcase_18 | AC | 162 ms
74,496 KB |
testcase_19 | AC | 161 ms
77,696 KB |
testcase_20 | AC | 155 ms
73,088 KB |
testcase_21 | AC | 159 ms
74,240 KB |
testcase_22 | AC | 135 ms
66,944 KB |
testcase_23 | AC | 135 ms
80,128 KB |
testcase_24 | AC | 129 ms
80,256 KB |
testcase_25 | AC | 175 ms
80,128 KB |
testcase_26 | AC | 172 ms
80,128 KB |
testcase_27 | AC | 179 ms
80,256 KB |
testcase_28 | AC | 172 ms
80,128 KB |
testcase_29 | AC | 148 ms
80,256 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); } 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; } } inline int rd_int(void){ int x; rd(x); return 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'); } } 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> 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 U cval, 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; } template <class T> struct DijkstraHeap{ int*hp; int*place; int size; char*visited; T*val; void malloc(int N){ hp = (int*)std::malloc(N*sizeof(int)); place = (int*)std::malloc(N*sizeof(int)); visited = (char*)std::malloc(N*sizeof(char)); val = (T*)std::malloc(N*sizeof(T)); } void free(){ std::free(hp); std::free(place); std::free(visited); std::free(val); } void walloc(int N, void **mem=&wmem){ walloc1d(&hp, N, mem); walloc1d(&place, N, mem); walloc1d(&visited, N, mem); walloc1d(&val, N, mem); } void init(int N){ int i; size = 0; for(i=(0);i<(N);i++){ place[i]=-1; } for(i=(0);i<(N);i++){ visited[i]=0; } } void up(int n){ int m; while(n){ m=(n-1)/2; if(val[hp[m]]<=val[hp[n]]){ break; } swap(hp[m],hp[n]); swap(place[hp[m]],place[hp[n]]); n=m; } } void down(int n){ int m; for(;;){ m=2*n+1; if(m>=size){ break; } if(m+1<size&&val[hp[m]]>val[hp[m+1]]){ m++; } if(val[hp[m]]>=val[hp[n]]){ break; } swap(hp[m],hp[n]); swap(place[hp[m]],place[hp[n]]); n=m; } } void change(int n, T v){ if(visited[n]||(place[n]>=0&&val[n]<=v)){ return; } val[n]=v; if(place[n]==-1){ place[n]=size; hp[size++]=n; up(place[n]); } else{ up(place[n]); } } int pop(void){ int res=hp[0]; place[res]=-1; size--; if(size){ hp[0]=hp[size]; place[hp[0]]=0; down(0); } visited[res]=1; return res; } } ; 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]; } } } ; template<class T> struct wgraph{ int N; int*es; int**edge; T**cost; graph g; void setDirectEdge(int N__, int M, int A[], int B[], T C[], void **mem = &wmem){ int i; N = N__; walloc1d(&es, N, mem); for(i=(0);i<(N);i++){ es[i] = 0; } for(i=(0);i<(M);i++){ es[A[i]]++; } walloc1d(&edge, N, mem); for(i=(0);i<(N);i++){ walloc1d(&edge[i], es[i], mem); } walloc1d(&cost, N, mem); for(i=(0);i<(N);i++){ walloc1d(&cost[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]; cost[A[i]][es[A[i]]++] = C[i]; } g.N = N; g.es = es; g.edge = edge; } template<class S> S getDistT(int a, int b, S unreachable = -1, void *mem = wmem){ int i; int j; DijkstraHeap<S> hp; hp.walloc(N, &mem); hp.init(N); hp.change(a,0); while(hp.size){ i = hp.pop(); if(i==b){ return hp.val[i]; } for(j=(0);j<(es[i]);j++){ hp.change(edge[i][j], hp.val[i]+cost[i][j]); } } return unreachable; } } ; struct dimcomp3{ int B; int C; dimcomp3(){ } ; dimcomp3(int b, int c){ B = b; C = c; } dimcomp3(int a, int b, int c){ B = b; C = c; } inline void set(int b, int c){ B = b; C = c; } inline void set(int a, int b, int c){ B = b; C = c; } inline int mask(int a, int b, int c){ return (a * B + b) * C + c; } inline int operator()(int a, int b, int c){ return (a * B + b) * C + c; } inline void para(int mask, int &a, int &b, int &c){ a = mask / (B*C); b = mask % (B*C) / C; c = mask % C; } inline void operator()(int mask, int &a, int &b, int &c){ a = mask / (B*C); b = mask % (B*C) / C; c = mask % C; } } ; int N; int cost[500][500]; int n; int m; int a[3000000]; int b[3000000]; int c[3000000]; wgraph<int> g; int main(){ int Lj4PdHRW; wmem = memarr; int i; int j; int k; int ni; int nj; int d; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; rd(N); dimcomp3 dm(2,N,N); int KL2GvlyY = rd_int(); for(Lj4PdHRW=(0);Lj4PdHRW<(KL2GvlyY);Lj4PdHRW++){ rd(i);i += (-1); rd(j);j += (-1); rd(k); cost[i][j] = k; } n = 2*N*N; for(i=(0);i<(N);i++){ for(j=(0);j<(N);j++){ for(d=(0);d<(4);d++){ { auto KrdatlYV = (i + dx[d]); auto ao_dF3pO = ( j + dy[d]); ni = KrdatlYV; nj = ao_dF3pO; } if(ni < 0 || nj < 0 || ni >= N || nj >= N){ continue; } for(k=(0);k<(2);k++){ arrInsert(m, m, a, dm(k,i,j), b, dm(k,ni,nj), c, 1+cost[ni][nj]); } arrInsert(m, m, a, dm(0,i,j), b, dm(1,ni,nj), c, 1); } } } g.setDirectEdge(n, m, a, b, c); wt_L(g.getDistT<long long>(0, dm(1,N-1,N-1))); wt_L('\n'); return 0; } // cLay varsion 20201115-1 // --- original code --- // int N, cost[500][500]; // int n, m, a[3d6], b[3d6], c[3d6]; // wgraph<int> g; // { // int i, j, k, ni, nj, d; // int dx[4] = {-1, 1, 0, 0}; // int dy[4] = {0, 0, -1, 1}; // rd(N); // dimcomp3 dm(2,N,N); // REP(rd_int()){ // rd(i--,j--,k); // cost[i][j] = k; // } // n = 2*N*N; // rep(i,N) rep(j,N) rep(d,4){ // (ni, nj) = (i + dx[d], j + dy[d]); // if(ni < 0 || nj < 0 || ni >= N || nj >= N) continue; // rep(k,2) arrInsert(m, m, a, dm(k,i,j), b, dm(k,ni,nj), c, 1+cost[ni][nj]); // arrInsert(m, m, a, dm(0,i,j), b, dm(1,ni,nj), c, 1); // } // g.setDirectEdge(n, m, a, b, c); // Wt(g.getDistT<ll>(0, dm(1,N-1,N-1))); // }