結果
問題 | No.1545 [Cherry 2nd Tune N] Anthem |
ユーザー |
![]() |
提出日時 | 2021-06-11 22:46:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 220 ms / 3,000 ms |
コード長 | 12,254 bytes |
コンパイル時間 | 4,453 ms |
コンパイル使用メモリ | 228,396 KB |
最終ジャッジ日時 | 2025-01-22 06:24:36 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 67 |
ソースコード
#pragma GCC optimize("Ofast")#pragma GCC optimize("unroll-loops")#pragma GCC optimize("inline")#include<bits/stdc++.h>using namespace std;template<class T> struct cLtraits_identity{using type = T;};template<class T> using cLtraits_try_make_signed =typename conditional<is_integral<T>::value,make_signed<T>,cLtraits_identity<T>>::type;template <class S, class T> struct cLtraits_common_type{using tS = typename cLtraits_try_make_signed<S>::type;using tT = typename cLtraits_try_make_signed<T>::type;using type = typename common_type<tS,tT>::type;};void*wmem;char memarr[96000000];template<class S, class T> inline auto min_L(S a, T b)-> typename cLtraits_common_type<S,T>::type{return (typename cLtraits_common_type<S,T>::type) a <= (typename cLtraits_common_type<S,T>::type) b ? a : b;}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 void rd(long long &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');}}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(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;}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 malloc(int N, int init_fg){malloc(N);if(init_fg){init(N);}}void walloc(int N, int init_fg, void **mem=&wmem){walloc(N,mem);if(init_fg){init(N);}}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];}}graph reverse(void **mem = &wmem){int i;int j;int k;graph g;g.N = N;walloc1d(&g.es, N, mem);walloc1d(&g.edge, N, mem);for(i=(0);i<(N);i++){g.es[i] = 0;}for(i=(0);i<(N);i++){for(j=(0);j<(es[i]);j++){g.es[edge[i][j]]++;}}for(i=(0);i<(N);i++){walloc1d(&g.edge[i], g.es[i], mem);}for(i=(0);i<(N);i++){g.es[i] = 0;}for(i=(0);i<(N);i++){for(j=(0);j<(es[i]);j++){k = edge[i][j];g.edge[k][g.es[k]++] = i;}}return g;}void getDist(int root, int res[], void *mem = wmem){int i;int j;int k;int*q;int s;int z;walloc1d(&q, N, &mem);for(i=(0);i<(N);i++){res[i]=-1;}res[root]=0;s=0;z=1;q[0]=root;while(z){i=q[s++];z--;for(j=(0);j<(es[i]);j++){k=edge[i][j];if(res[k]>=0){continue;}res[k]=res[i]+1;q[s+z++]=k;}}}int getDist(int a, int b, void *mem = wmem){int i;int j;int k;int*q;int s;int z;int*d;if(a==b){return 0;}walloc1d(&d, N, &mem);walloc1d(&q, N, &mem);for(i=(0);i<(N);i++){d[i] = -1;}d[a] = 0;s = 0;z = 1;q[0] = a;while(z){i = q[s++];z--;for(j=(0);j<(es[i]);j++){k = edge[i][j];if(d[k] >= 0){continue;}d[k] = d[i] + 1;if(k==b){return d[k];}q[s+z++] = k;}}return -1;}};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> void getDist(int root, S res[], S unreachable = -1, void *mem = wmem){int i;int j;DijkstraHeap<S> hp;hp.walloc(N, &mem);hp.init(N);hp.change(root,0);while(hp.size){i = hp.pop();for(j=(0);j<(es[i]);j++){hp.change(edge[i][j], hp.val[i]+cost[i][j]);}}for(i=(0);i<(N);i++){res[i] = (hp.visited[i] ? hp.val[i] : unreachable);}}};int N;int S;int T;int K;int M;int A[200000];int B[200000];long long X[200000];long long Y[200000];int nn;int mm;int aa[2000000];int bb[2000000];long long cc[2000000];long long d[2000000];int bk[2000000];int ress;int res[2000000];wgraph<long long> g;int main(){int i, k;wmem = memarr;rd(N);rd(S);S += (-1);rd(T);T += (-1);rd(K);{int Lj4PdHRW;for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){rd(X[Lj4PdHRW]);}}rd(M);{int e98WHCEY;for(e98WHCEY=(0);e98WHCEY<(M);e98WHCEY++){rd(A[e98WHCEY]);A[e98WHCEY] += (-1);rd(B[e98WHCEY]);B[e98WHCEY] += (-1);rd(Y[e98WHCEY]);}}for(i=(0);i<(M);i++){Y[i] += X[B[i]];}nn = N * K;for(k=(0);k<(K);k++){for(i=(0);i<(M);i++){arrInsert(mm, mm, aa, N*k+A[i], bb, N*min_L(K-1, k+1)+B[i], cc, Y[i]);}}g.setDirectEdge(nn,mm,aa,bb,cc);g.getDist(S,d);if(d[(K-1)*N+T] == -1){wt_L("Impossible");wt_L('\n');return 0;}wt_L("Possible");wt_L('\n');wt_L(d[(K-1)*N+T]+X[S]);wt_L('\n');for(i=(0);i<(nn);i++){if(d[i] >= 0){int j;for(j=(0);j<(g.es[i]);j++){if(d[g.edge[i][j]] == d[i]+g.cost[i][j]){bk[g.edge[i][j]] = i;}}}}i = (K-1) * N + T;for(;;){res[ress++] = i % N;if(i == S){break;}i = bk[i];}reverse(res,res+ress);wt_L(ress);wt_L('\n');{int jbtyPBGc;if(ress==0){wt_L('\n');}else{for(jbtyPBGc=(0);jbtyPBGc<(ress-1);jbtyPBGc++){wt_L(res[jbtyPBGc]+1);wt_L(' ');}wt_L(res[jbtyPBGc]+1);wt_L('\n');}}return 0;}// cLay version 20210611-1 [beta]// --- original code ---// int N, S, T, K, M, A[2d5], B[];// ll X[], Y[];// int nn, mm, aa[2d6], bb[]; ll cc[], d[];// int bk[], ress, res[];// wgraph<ll> g;// {// rd(N,S--,T--,K,X(N),M,(A--,B--,Y)(M));// rep(i,M) Y[i] += X[B[i]];//// nn = N * K;// rep(k,K) rep(i,M) arrInsert(mm, mm, aa, N*k+A[i], bb, N*min(K-1,k+1)+B[i], cc, Y[i]);// g.setDirectEdge(nn,mm,aa,bb,cc);// g.getDist(S,d);//// if(d[(K-1)*N+T] == -1) wt("Impossible"), return 0;// wt("Possible");// wt(d[(K-1)*N+T]+X[S]);//// rep(i,nn) if(d[i] >= 0) rep(j,g.es[i]) if(d[g.edge[i][j]] == d[i]+g.cost[i][j]) bk[g.edge[i][j]] = i;// i = (K-1) * N + T;// for(;;){// res[ress++] = i % N;// if(i == S) break;// i = bk[i];// }// reverse(res,res+ress);// wt(ress);// wt(res(ress)+1);// }