Submission #298274

#	Time	Username	Problem	Language	Result	Execution time	Memory
298274		shayan_p	Sky Walking (IOI19_walk)	C++17	0 / 100	4101 ms	519948 KiB

walk

#include<bits/stdc++.h>
#include "walk.h"

#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const int maxn = 13e6 + 10, inf = 2e9;
const ll INF = 2e18;

ll dis[maxn];
bool mark[maxn];
vector<pii> v[maxn];

ll digi(int a, int b){
    fill(dis, dis + maxn, INF);
    priority_queue<pli, vector<pli>, greater<pli> > pq;
    dis[a] = 0;
    pq.push({0, a});
    while(sz(pq)){
	int u = pq.top().S;
	pq.pop();
	if(mark[u])
	    continue;
	mark[u] = 1;
	for(auto [y, c] : v[u]){
	    if(dis[u] + c < dis[y])
		dis[y] = dis[u] + c, pq.push({dis[y], y});
	}
    }
    return dis[b];
}

map<pii, int> mp;
int C = 0;
int up[maxn];

void add_edge(int a, int b, int h){
    assert(mp.count({a, h}));
    assert(mp.count({b, h}));
    int A = mp[{a, h}], B = mp[{b, h}];
    v[A].PB({B, abs(b-a)});
    v[B].PB({A, abs(b-a)});    
}

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int src, int snk){
    vector<int> hs = h;
    for(int x : y)
	hs.PB(x);
    sort(hs.begin(), hs.end());
    hs.resize( unique(hs.begin(), hs.end()) - hs.begin() );

    int n = sz(x), m = sz(y);
    vector<int> idsx(n), idsy(m);
    iota(idsx.begin(), idsx.end(), 0);
    iota(idsy.begin(), idsy.end(), 0);

    sort(idsx.begin(), idsx.end(), [&](int i, int j){ return h[i] > h[j]; } );
    sort(idsy.begin(), idsy.end(), [&](int i, int j){ return y[i] > y[j]; } );


    for(int i = 0; i < n; i++){
	up[i] = inf;
    }
    
    auto build = [&](int id, int h){
		     if(mp.count({x[id], h}) == 0){
			 mp[{x[id], h}] = C++;
			 if(up[id] != inf){
			     int A = C-1, B = mp[{x[id], up[id]}];
			     v[A].PB({B, abs(h - up[id])});
			     v[B].PB({A, abs(h - up[id])});			     
			 }
			 up[id] = h;
		     }
		 };
    
    int ptx = 0, pty = 0;
    set<int> ids;
    while(ptx < n || pty < m){
	if(ptx == n || (pty != m && h[idsx[ptx]] < y[idsy[pty]])){
	    auto itl = ids.lower_bound(l[ idsy[pty] ]);
	    auto itr = ids.upper_bound(r[ idsy[pty] ]);
	    int LSTX = -1;
	    for(auto it = itl; it != itr; it++){
		build(*it, y[idsy[pty]]);
		if(LSTX != -1)
		    add_edge(LSTX, x[*it], y[idsy[pty]]);
		LSTX = x[*it];
	    }
	    pty++;
	}
	else{
	    ids.insert(idsx[ptx]);
	    ptx++;
	}	    
    }

    for(int i = 0; i < n; i++){
	build(i, 0);
    }

    return digi(mp[{x[src], 0}], mp[{x[snk], 0}]);
}

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