Submission #436545

#	Time	Username	Problem	Language	Result	Execution time	Memory
436545		rqi	Sky Walking (IOI19_walk)	C++14	57 / 100	3430 ms	1048580 KiB

walk

    #include "walk.h"
    #include <bits/stdc++.h>
    using namespace std;
     
    typedef vector<int> vi;
    typedef pair<int, int> pi;
    typedef vector<pi> vpi;
    typedef long long ll;
    typedef vector<ll> vl;
     
    #define f first
    #define s second
    #define mp make_pair
    #define pb push_back
    #define bk back()
    #define ins insert
    #define lb lower_bound
     
    #define sz(x) (int)(x).size()
    #define all(x) begin(x), end(x)
     
    const ll INF = 1e18;
     
    int n, m;
     
    const int mx = 100005;
    vector<pair<int, ll>> adj[2000005];
    ll dij[2000005];
     
    ll solveShort(int N, int A, int B){
    	for(int i = 0; i < N; i++){
    		dij[i] = INF;
    	}
     
    	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    	dij[A] = 0;
    	pq.push(mp(dij[A], A));
     
    	while(sz(pq)){
    		ll d = pq.top().f;
    		int node = pq.top().s;
    		pq.pop();
    		if(dij[node] < d) continue;
    		for(auto u: adj[node]){
    			ll new_d = d+u.s;
    			if(dij[u.f] <= new_d) continue;
    			dij[u.f] = new_d;
    			pq.push(mp(dij[u.f], u.f));
    		}
    	}
     
    	if(dij[B] == INF) return -1;
    	return dij[B];
    }
     
    ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
    	n = sz(x);
    	m = sz(l);
     
     
    	if(s == 0 && g == n-1){
    		// cout << "HI" << "\n";
    		// cout.flush();
    		vi ending_at[mx];
    		for(int i = 0; i < m; i++){
    			ending_at[r[i]].pb(i);
    		}
    		vi starting_at[mx];
    		for(int i = 0; i < m; i++){
    			starting_at[l[i]].pb(i);
    		}
     
    		ending_at[0].pb(m);
    		starting_at[n-1].pb(m+1);
    		l.pb(0);
    		r.pb(0);
    		l.pb(n-1);
    		r.pb(n-1);
     
    		y.pb(0);
    		y.pb(0);

    		// for(int i = 0; i < sz(y); i++){
    		// 	cout << i << " " << y[i] << "\n";
    		// }
     
    		vector<pair<pi, ll>> eds;
     
    		set<pi> cur_sky_heights; // height, sky index
    		cur_sky_heights.ins(mp(y[m], m));
    		for(int i = 0; i < n; i++){
    			//do updates
    			for(auto sky: ending_at[i]){
    				cur_sky_heights.erase(mp(y[sky], sky));
    			}
    			for(auto sky: starting_at[i]){
    				cur_sky_heights.ins(mp(y[sky], sky));
    			}

    			// cout << "i=" << i << "\n";
    			// for(auto u: cur_sky_heights){
    			// 	cout << u.f << " " << u.s << "\n";
    			// }
     
    			for(auto sky: ending_at[i]){
    				auto it_above = cur_sky_heights.lb(mp(y[sky], 0));
    				auto it_below = cur_sky_heights.lb(mp(y[sky]+1, 0));
     
    				if(it_above != cur_sky_heights.end()){
    					int to_sky = it_above->s;
    					eds.pb(mp(mp(sky, to_sky), abs(y[sky]-y[to_sky])));
    				}
    				if(it_below != cur_sky_heights.begin()){
    					it_below = prev(it_below);
    					int to_sky = it_below->s;
    					eds.pb(mp(mp(sky, to_sky), abs(y[sky]-y[to_sky])));
    				}
    			}
    		}
     
    		for(auto u: eds){
    			// cout << u.f.f << " " << u.f.s << " " << u.s << "\n";
    			adj[u.f.f].pb(mp(u.f.s, u.s));
    		}
     
    		//m is source, m+1 is sink
    		ll ans = solveShort(m+2, m, m+1);
    		if(ans == -1) return ans;

    		return x[n-1]-x[0]+ans;
    	}
     
    	vi sort_by_y;
    	for(int i = 0; i < m; i++){
    		sort_by_y.pb(i);
    	}
    	sort(all(sort_by_y), [&](const int& a, const int& b){
    		return y[a] > y[b];
    	});
     
    	vi sort_by_h;
    	for(int i = 0; i < n; i++){
    		sort_by_h.pb(i);
    	}
    	sort(all(sort_by_h), [&](const int& a, const int& b){
    		return h[a] > h[b];
    	});
     
    	set<int> active_buildings;
     
    	int sort_by_h_ind = 0;
     
    	vector<pair<pi, pi>> point_eds; //building index, height
     
     
    	// cout << "HI" << "\n";
    	// cout.flush();
    	for(auto sky: sort_by_y){
    		while(sort_by_h_ind < sz(sort_by_h)){
    			int building_ind = sort_by_h[sort_by_h_ind];
    			if(h[building_ind] >= y[sky]){
    				active_buildings.ins(building_ind);
    				sort_by_h_ind++;
    			}
    			else{
    				break;
    			}
    		}
     
    		auto it = active_buildings.lb(l[sky]);
    		assert(*it == l[sky]);
     
    		while(true){
    			assert(next(it) != active_buildings.end());
    			point_eds.pb(mp(mp(*it, y[sky]), mp(*next(it), y[sky])));
     
    			if(*next(it) == r[sky]) break;
     
    			it = next(it);
    		}
    	}
     
     
    	// cout << "HI" << "\n";
    	// cout.flush();
    	set<int> each_building[mx]; //sky walk heights for each building
    	for(auto u: point_eds){
    		// cout << u.f.f << " " << u.f.s << " " << u.s.f << " " << u.s.s << "\n";
    		each_building[u.f.f].ins(u.f.s);
    		each_building[u.s.f].ins(u.s.s);
    	}
     
    	for(int i = 0; i < n; i++){
    		each_building[i].ins(0);
    		each_building[i].ins(h[i]);
    	}
     
    	for(int i = 0; i < n; i++){
    		auto it = each_building[i].begin();
    		while(next(it) != each_building[i].end()){
     
    			int y1 = *it;
    			int y2 = *next(it);
    			point_eds.pb(mp(mp(i, y1), mp(i, y2)));
     
    			it = next(it);
    		}
    	}
     
    	map<pi, int> compress;
    	vpi all_nodes;
    	for(auto u: point_eds){
    		all_nodes.pb(u.f);
    		all_nodes.pb(u.s);
    	}
    	int cnt = 0;
    	for(auto u: all_nodes){
    		if(!compress.count(u)){
    			compress[u] = cnt;
    			cnt++;
    		}
    	}
     
    	// for(auto u: point_eds){
    	// 	cout << u.f.f << " " << u.f.s << " " << u.s.f << " " << u.s.s << "\n";
    	// }
    	for(auto u: point_eds){
    		ll dist = INF;
    		if(u.f.f == u.s.f){
    			dist = abs(u.s.s-u.f.s);
    		}
    		else{
    			assert(u.s.s == u.f.s);
    			dist = abs(x[u.s.f]-x[u.f.f]);
    		}
    		int a = compress[u.f];
    		int b = compress[u.s];
    		adj[a].pb(mp(b, dist));
    		adj[b].pb(mp(a, dist));
     
    		// cout << a << " " << b << " " << dist << "\n";
    	}
     
     
    	return solveShort(cnt, compress[mp(s, 0)], compress[mp(g, 0)]);
    }

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