結果
問題 | No.1069 電柱 / Pole (Hard) |
ユーザー |
![]() |
提出日時 | 2020-05-30 00:57:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 161 ms / 2,000 ms |
コード長 | 10,748 bytes |
コンパイル時間 | 3,955 ms |
コンパイル使用メモリ | 230,896 KB |
最終ジャッジ日時 | 2025-01-10 18:50:39 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 79 |
ソースコード
#pragma GCC optimize ("Ofast")#include<bits/stdc++.h>using namespace std;void *wmem;char memarr[96000000];template<class S, class T> inline S max_L(S a,T b){return a>=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);}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');}}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');}}}template<class T> inline T pow2_L(T a){return a*a;}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 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];}}};template<class T> struct wgraph{int N;int *es;int **edge;T **cost;graph g;void setEdge(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]]++;es[B[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];edge[B[i]][es[B[i]]] = A[i];cost[A[i]][es[A[i]]++] = C[i];cost[B[i]][es[B[i]]++] = C[i];}g.N = N;g.es = es;g.edge = edge;}};int N;int M;int K;int S;int T;int X[200000];int Y[200000];int A[200000];int B[200000];double c[200000];double dis[200000];wgraph<double> g;int sz;int ok;int done;double cost[10];vector<int> path[10];vector<int> cpath;priority_queue<pair<double,vector<int>>> q;DijkstraHeap<double> hp;int bk[2000];vector<int> rt;int main(){wmem = memarr;int i;int j;int k;int b;int cr;rd(N);rd(M);rd(K);rd(S);S += (-1);rd(T);T += (-1);{int Lj4PdHRW;for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){rd(X[Lj4PdHRW]);rd(Y[Lj4PdHRW]);}}{int e98WHCEY;for(e98WHCEY=(0);e98WHCEY<(M);e98WHCEY++){rd(A[e98WHCEY]);A[e98WHCEY] += (-1);rd(B[e98WHCEY]);B[e98WHCEY] += (-1);}}for(i=(0);i<(M);i++){c[i] = sqrt((pow2_L((X[A[i]]-X[B[i]])))+(pow2_L((Y[A[i]]-Y[B[i]]))));}g.setEdge(N,M,A,B,c);hp.malloc(N);for(;;){if(q.size()==0 && ok){break;}if(q.size()){cpath = q.top().second;for(i=(0);i<(ok);i++){if(cpath == path[i]){q.pop();goto WYIGIcGE;}}cost[ok] = -q.top().first;path[ok] = cpath;ok++;if(ok==K){break;}}for(b=(0);b<(max_L(1, (int)cpath.size()-1));b++){hp.init(N);hp.change(S,0);cr = 0;bk[S] = -1;while(hp.size){i = hp.pop();for(j=(0);j<(g.es[i]);j++){k = g.edge[i][j];if(cpath.size() && cr==b){int x;if(k==cpath[cr+1]){continue;}for(x=(0);x<(ok-1);x++){int y;for(y=(0);y<(b+1);y++){if(path[x][y] != cpath[y]){goto jbtyPBGc;}}if(k==path[x][cr+1]){goto YREPHmFM;}jbtyPBGc:;}}if(cpath.size() && cr<b && k != cpath[cr+1]){continue;}if(hp.visited[k]){continue;}if(hp.place[k]==-1 || hp.val[k] > hp.val[i]+g.cost[i][j]){bk[k] = i;hp.change(k,hp.val[i]+g.cost[i][j]);}YREPHmFM:;}cr++;}if(hp.visited[T]==0){continue;}rt.clear();i = T;while(i >= 0){rt.push_back(i);i = bk[i];}reverse(rt.begin(), rt.end());q.push(make_pair(-hp.val[T], rt));}WYIGIcGE:;}for(i=(0);i<(K);i++){if(i < ok){wt_L(cost[i]);wt_L('\n');}else{wt_L(-1);wt_L('\n');}}return 0;}// cLay varsion 20200509-1// --- original code ---// int N, M, K, S, T, X[2d5], Y[2d5], A[2d5], B[2d5];// double c[2d5], dis[2d5];// wgraph<double> g;//// int sz, ok, done;// double cost[10];// vector<int> path[10], cpath;//// priority_queue<pair<double,vector<int>>> q;//// DijkstraHeap<double> hp;// int bk[2000];// vector<int> rt;//// {// int i, j, k, b, cr;//// rd(N,M,K,S--,T--,(X,Y)(N),(A--,B--)(M));// rep(i,M) c[i] = sqrt( (X[A[i]]-X[B[i]])**2 + (Y[A[i]]-Y[B[i]])**2 );// g.setEdge(N,M,A,B,c);//// hp.malloc(N);//// for(;;){// if(q.size()==0 && ok) break;// if(q.size()){// cpath = q.top().second;// rep(i,ok) if(cpath == path[i]){// q.pop();// break_continue;// }// cost[ok] = -q.top().first;// path[ok] = cpath;// // wt(cost[ok],":",cpath(cpath.size()));// ok++;// if(ok==K) break;// }// rep(b,max(1,(int)cpath.size()-1)){// hp.init(N);// hp.change(S,0);// cr = 0;// bk[S] = -1;// while(hp.size){// i = hp.pop();// rep(j,g.es[i]){// k = g.edge[i][j];// if(cpath.size() && cr==b){// if(k==cpath[cr+1]) continue;// rep(x,ok-1){// rep(y,b+1) if(path[x][y] != cpath[y]) break_continue;// if(k==path[x][cr+1]) break_continue;// }// }// if(cpath.size() && cr<b && k != cpath[cr+1]) continue;// if(hp.visited[k]) continue;// if(hp.place[k]==-1 || hp.val[k] > hp.val[i]+g.cost[i][j]){// bk[k] = i;// hp.change(k,hp.val[i]+g.cost[i][j]);// }// }// cr++;// }// if(hp.visited[T]==0) continue;// rt.clear();// i = T;// while(i >= 0){// rt.push_back(i);// i = bk[i];// }// reverse(rt.begin(), rt.end());// q.push(make_pair(-hp.val[T], rt));// // wt(b,":",cpath(cpath.size()),":",rt(rt.size()),":",hp.val[T]);// }// }//// rep(i,K) wt(if[i < ok, cost[i], -1]);// }