이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include "walk.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
int n,m;
vector<unordered_set<int>> twr,br;
vector<pair<ll,ll>> tower;
vector<pair<ll,pair<ll,ll>>> bridge;
map<pair<int,int>,ll> dist;
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g)
{
n=x.size(), m=l.size();
twr.resize(n), br.resize(m);
for(int i=0;i<n;i++) tower.pb({h[i],x[i]});
for(int i=0;i<m;i++) bridge.pb({y[i],{x[l[i]],x[r[i]]}});
pair<ll,ll> ps=tower[s], pg=tower[g];
sort(tower.begin(),tower.end()); reverse(tower.begin(),tower.end());
sort(bridge.begin(),bridge.end()); reverse(bridge.begin(),bridge.end());
for(int i=0;i<n;i++)
{
if(tower[i]==ps) s=i;
if(tower[i]==pg) g=i;
}
twr[g].insert(-1);
set<pair<int,int>> st;
int ptr=0;
for(int i=0;i<m;i++)
{
int H=bridge[i].x,L=bridge[i].y.x,R=bridge[i].y.y;
if(L>R) swap(L,R);
while(ptr<n)
{
if(tower[ptr].x<H) break;
st.insert({tower[ptr].y,ptr});
ptr++;
}
auto itL=st.lower_bound({L,-1}), itR=st.lower_bound({R+1,-1});
while(itL!=itR && itL!=st.end())
{
twr[(*itL).y].insert(i);
br[i].insert((*itL).y);
itL++;
}
}
set<pair<int,int>> vis;
dist[{s,-1}]=0;
priority_queue<pair<pair<ll,pair<int,int>>,bool>> dij;
dij.push({{0,{s,-1}},1});
while(!dij.empty())
{
ll d=-dij.top().x.x; int T=dij.top().x.y.x, B=dij.top().x.y.y; bool which=dij.top().y;
if(T==g && B==-1) break;
twr[T].erase(B); if(B!=-1)br[B].erase(T);
dij.pop();
if(vis.count({T,B})) continue;
vis.insert({T,B});
if(which) for(int v:twr[T])
{
if(v==B) continue;
if(vis.count({T,v})) continue;
ll newD=d+abs((v==-1?0:bridge[v].x)-(B==-1?0:bridge[B].x));
if(newD<(dist.count({T,v})?dist[{T,v}]:2e18))
{
dist[{T,v}]=newD;
dij.push({{-newD,{T,v}},which^1});
}
}
else if(B!=-1) for(int v:br[B])
{
if(v==T) continue;
if(vis.count({v,B})) continue;
ll newD=d+abs(tower[v].y-tower[T].y);
if(newD<(dist.count({v,B})?dist[{v,B}]:2e18))
{
dist[{v,B}]=newD;
dij.push({{-newD,{v,B}},which^1});
}
}
}
if(dist.count({g,-1})) return dist[{g,-1}];
return -1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |