Submission #1111105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111105		epicci23	Sky Walking (IOI19_walk)	C++17	0 / 100	93 ms	18180 KiB

walk

#include "bits/stdc++.h"
#include "walk.h"
#define ll long long
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (ll)a.size()
using namespace std;

const ll INF = 1e18;
vector<vector<array<ll,2>>> v;
vector<array<ll,2>> nodes;

inline ll get_ind(ll x,ll y){
  ll it = lower_bound(all(nodes),array<ll,2>{x,y})-nodes.begin();
  return it;
}

ll dijkstra(ll _s,ll _t){
  vector<ll> dist(sz(v)+5,INF);
  dist[_s]=0;
  priority_queue<array<ll,2>> pq;
  pq.push({{0,_s}});
  while(!pq.empty()){
  	ll c = pq.top()[1];
  	ll d = -pq.top()[0];
  	pq.pop();
  	if(d>dist[c]) continue;
  	for(array<ll,2> u:v[c]){
      if(u[1]+d<dist[u[0]]){
      	dist[u[0]]=d+u[1];
      	pq.push({-dist[u[0]],u[0]});
      }
  	}
  }
  return dist[_t];
}




ll min_distance(vector<int> X,vector<int> H, vector<int> L,vector<int> R,vector<int> Y, int _st, int _tt){
  ll n = sz(X),m = sz(L);

  ll ar[n+5],he[n+5],l[m+5],r[m+5],y[m+5];
  for(ll i=1;i<=n;i++) ar[i] = X[i-1];
  for(ll i=1;i<=n;i++) he[i] = H[i-1];
  
  for(ll i=1;i<=n;i++){
    nodes.push_back({ar[i],0});
    nodes.push_back({ar[i],he[i]});
  }

  for(ll i=1;i<=m;i++) l[i]=L[i-1];
  for(ll i=1;i<=m;i++) r[i]=R[i-1];
  for(ll i=1;i<=m;i++) y[i]=Y[i-1];

  vector<array<ll,3>> sky;
  for(ll i=1;i<=m;i++) sky.push_back({y[i],l[i],r[i]});
  sort(all(sky));

  multiset<ll> xs;
  for(ll i=1;i<=n;i++) xs.insert(ar[i]);

  vector<ll> lol;

  for(ll i=1;i<=n;i++) lol.push_back(i);

  sort(all(lol),[&](ll a,ll b){
    return he[a] < he[b];
  });

  ll _p=0;
 
  for(auto x:sky){
  	nodes.push_back({ar[x[1]],x[0]});
  	nodes.push_back({ar[x[2]],x[0]});
    while(_p<n && he[lol[_p]]<x[0]) xs.erase(xs.find(ar[lol[_p++]]));
    auto it = xs.lower_bound(ar[x[1]]);
    while(it!=xs.end() && (*it)<=ar[x[2]]){
      nodes.push_back({(*it),x[0]});
      it++;
    }
  }

  sort(all(nodes));
  nodes.erase(unique(all(nodes)),nodes.end());
  v.resize(sz(nodes)+5);
  
  map<ll,vector<ll>> mp;
  for(auto x:nodes) mp[x[0]].push_back(x[1]);
  for(auto x:mp) sort(all(mp[x.first]));

  for(ll i=1;i<=n;i++){
  	v[get_ind(ar[i],0)].push_back({get_ind(ar[i],he[i]),he[i]});
  	v[get_ind(ar[i],he[i])].push_back({get_ind(ar[i],0),he[i]});
  	for(ll j=1;j<sz(mp[ar[i]]);j++){
      if(mp[ar[i]][j]>he[i]) break;
      ll _a = get_ind(ar[i],mp[ar[i]][j]);
      ll _b = get_ind(ar[i],mp[ar[i]][j-1]);
      ll _c = mp[ar[i]][j] - mp[ar[i]][j-1];
      assert(_c>=0);
      v[_a].push_back({_b,_c});
      v[_b].push_back({_a,_c});
  	}
  }

  _p=0;
  xs.clear();
  for(ll i=1;i<=n;i++) xs.insert(ar[i]);

  
  for(auto x:sky){
  	vector<array<ll,2>> curi;
  	curi.push_back({ar[x[1]],x[0]});
    curi.push_back({ar[x[2]],x[0]});
  	for(int j=x[1];j<=x[2];j++) if(x[0]<=he[j]) curi.push_back({ar[j],x[0]});
  	sort(all(curi));
    curi.erase(unique(all(curi)),curi.end());


  	for(ll j=1;j<sz(curi);j++){
      ll _a = get_ind(curi[j][0],curi[j][1]);
      ll _b = get_ind(curi[j-1][0],curi[j-1][1]);
      ll _c = curi[j][0] - curi[j-1][0];
      assert(_c>=0);
      v[_a].push_back({_b,_c});
      v[_b].push_back({_a,_c});
    }
  }
   

  /*for(auto x:sky){
  	vector<array<ll,2>> curi;
    curi.push_back({ar[x[1]],x[0]});
    curi.push_back({ar[x[2]],x[0]});
    

    while(_p<n && he[lol[_p]]<x[0]) xs.erase(xs.find(ar[lol[_p++]]));

    auto it = xs.lower_bound(ar[x[1]]);
    while(it!=xs.end() && (*it)<=ar[x[2]]){
      curi.push_back({(*it),x[0]});
      it++;
    }

    sort(all(curi));
   //curi.erase(unique(all(curi)),curi.end());
    for(ll j=1;j<sz(curi);j++){
      ll _a = get_ind(curi[j][0],curi[j][1]);
      ll _b = get_ind(curi[j-1][0],curi[j-1][1]);
      ll _c = curi[j][0] - curi[j-1][0];
      assert(_c>=0);
      v[_a].push_back({_b,_c});
      v[_b].push_back({_a,_c});
    }
  }*/
 
  ll ans = dijkstra(get_ind(ar[_st],0),get_ind(ar[_tt],0));
  if(ans==INF) return -1;
  return ans;
}

/*void _(){
  ll n,m,_st,_tt;
  cin >> n >> m >> _st >> _tt;
  ll ar[n+5],he[n+5],l[m+5],r[m+5],y[m+5];
  for(ll i=1;i<=n;i++) cin >> ar[i];
  for(ll i=1;i<=n;i++) cin >> he[i];
  
  
  for(ll i=1;i<=n;i++){
    nodes.push_back({ar[i],0});
    nodes.push_back({ar[i],he[i]});
  }

  for(ll i=1;i<=m;i++) cin >> l[i];
  for(ll i=1;i<=m;i++) cin >> r[i];
  for(ll i=1;i<=m;i++) cin >> y[i];

  vector<array<ll,3>> sky;
  for(ll i=1;i<=m;i++) sky.push_back({y[i],l[i],r[i]});
  sort(all(sky));

  multiset<ll> xs;
  for(ll i=1;i<=n;i++) xs.insert(ar[i]);
  vector<ll> lol;
  for(ll i=1;i<=n;i++) lol.push_back(i);
  sort(all(lol),[&](ll a,ll b){
    return he[a] < he[b];
  });

  ll _p=0;
 
  for(auto x:sky){
  	nodes.push_back({ar[x[1]],x[0]});
  	nodes.push_back({ar[x[2]],x[0]});
    while(_p<n && he[lol[_p]]<x[0]) xs.erase(xs.find(ar[lol[_p++]]));
    auto it = xs.lower_bound(ar[x[1]]);
    while(it!=xs.end() && (*it)<=ar[x[2]]){
      nodes.push_back({(*it),x[0]});
      it++;
    }
  }

  sort(all(nodes));
  nodes.erase(unique(all(nodes)),nodes.end());
  v.resize(sz(nodes)+5);
  
  map<ll,vector<ll>> mp;
  for(auto x:nodes) mp[x[0]].push_back(x[1]);
  for(auto x:mp) sort(all(mp[x.first]));

  for(ll i=1;i<=n;i++){
  	v[get_ind(ar[i],0)].push_back({get_ind(ar[i],he[i]),he[i]});
  	v[get_ind(ar[i],he[i])].push_back({get_ind(ar[i],0),he[i]});
  	for(ll j=1;j<sz(mp[ar[i]]);j++){
      if(mp[ar[i]][j]>he[i]) break;
      ll _a = get_ind(ar[i],mp[ar[i]][j]);
      ll _b = get_ind(ar[i],mp[ar[i]][j-1]);
      ll _c = mp[ar[i]][j] - mp[ar[i]][j-1];
      v[_a].push_back({_b,_c});
      v[_b].push_back({_a,_c});
  	}
  }

  _p=0;
  xs.clear();
  for(ll i=1;i<=n;i++) xs.insert(ar[i]);

  for(auto x:sky){
  	vector<array<ll,2>> curi;
    curi.push_back({ar[x[1]],x[0]});
    curi.push_back({ar[x[2]],x[0]});
    

    while(_p<n && he[lol[_p]]<x[0]) xs.erase(xs.find(ar[lol[_p++]]));

    auto it = xs.lower_bound(ar[x[1]]);
    while(it!=xs.end() && (*it)<=ar[x[2]]){
      curi.push_back({(*it),x[0]});
      it++;
    }

    sort(all(curi));
    curi.erase(unique(all(curi)),curi.end());
    for(ll j=1;j<sz(curi);j++){
      ll _a = get_ind(curi[j][0],curi[j][1]);
      ll _b = get_ind(curi[j-1][0],curi[j-1][1]);
      ll _c = curi[j][0] - curi[j-1][0];
      v[_a].push_back({_b,_c});
      v[_b].push_back({_a,_c});
    }
  }
 
  ll ans = dijkstra(get_ind(ar[_st],0),get_ind(ar[_tt],0));
  cout << ans << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  ll tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43