Submission #1216840

#TimeUsernameProblemLanguageResultExecution timeMemory
1216840loiiii12358Sky Walking (IOI19_walk)C++20
14 / 100
2623 ms280968 KiB
#include "walk.h" #include <bits/stdc++.h> using namespace std; #define int long long struct segment{ int pos,ma; segment(){ pos=ma=0; } segment(int a,int b){ pos=a; ma=b; } }; segment merge(segment a,segment b){ segment ans; if(a.ma>b.ma){ ans=a; }else{ ans=b; } return ans; } int N; vector<int> H,X; vector<segment> seg; void build(int id,int l,int r){ if(l==r){ seg[id]=segment(l,H[l]); return; } int m=(l+r)/2; build(id*2,l,m); build(id*2+1,m+1,r); seg[id]=merge(seg[id*2],seg[id*2+1]); } segment query(int id,int l,int r,int L,int R){ if(l>R||r<L){ return segment(); }else if(l>=L&&r<=R){ return seg[id]; } int m=(l+r)/2; return merge(query(id*2,l,m,L,R),query(id*2+1,m+1,r,L,R)); } int cnt; map<pair<int,int>,int> tran; vector<set<int>> nodes; vector<vector<pair<int,int>>> edges; priority_queue<pair<int,int>> pq; vector<int> dist; void add(int l,int r,int y){ if(l+1>r-1){ if(!tran.count({X[l],y})){ tran[{X[l],y}]=cnt++; nodes[l].insert(y); } if(!tran.count({X[r],y})){ tran[{X[r],y}]=cnt++; nodes[r].insert(y); } edges[tran[{X[r],y}]].push_back({tran[{X[l],y}],X[r]-X[l]}); edges[tran[{X[l],y}]].push_back({tran[{X[r],y}],X[r]-X[l]}); return; } segment tmp=query(1,0,N-1,l+1,r-1); if(tmp.ma>=y){ add(l,tmp.pos,y); add(tmp.pos,r,y); }else{ if(!tran.count({X[l],y})){ tran[{X[l],y}]=cnt++; nodes[l].insert(y); } if(!tran.count({X[r],y})){ tran[{X[r],y}]=cnt++; nodes[r].insert(y); } edges[tran[{X[r],y}]].push_back({tran[{X[l],y}],X[r]-X[l]}); edges[tran[{X[l],y}]].push_back({tran[{X[r],y}],X[r]-X[l]}); } } long long min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t s, int32_t g) { N=x.size(); int m=l.size(); H.resize(N);seg.resize(4*N);X.resize(N);edges.resize(15*m);nodes.resize(N); for(int i=0;i<N;i++){ H[i]=h[i]; X[i]=x[i]; } build(1,0,N-1); for(int i=0;i<m;i++){ add(l[i],r[i],y[i]); } tran[{x[s],0}]=cnt++;tran[{x[g],0}]=cnt++; nodes[s].insert(0);nodes[g].insert(0); for(int i=0;i<N;i++){ int last=-1; for(auto j:nodes[i]){ if(last!=-1){ edges[tran[{x[i],last}]].push_back({tran[{x[i],j}],j-last}); edges[tran[{x[i],j}]].push_back({tran[{x[i],last}],j-last}); } last=j; } } dist.resize(cnt,1e18); pq.push({0,tran[{x[s],0}]}); dist[tran[{x[s],0}]]=0; while(!pq.empty()){ int u=pq.top().second,t=-pq.top().first; pq.pop(); if(dist[u]!=t){ continue; } for(int i=0;i<edges[u].size();i++){ int v=edges[u][i].first; if(dist[v]>t+edges[u][i].second){ dist[v]=t+edges[u][i].second; pq.push({-dist[v],v}); } } } if(dist[tran[{x[g],0}]]==1e18){ return -1; } return dist[tran[{x[g],0}]]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...