Submission #1206664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206664		thelegendary08	Sky Walking (IOI19_walk)	C++17	10 / 100	4128 ms	1114112 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i =k; i<n; i++)
#define vi vector<int>
#define pii pair<int,int>
#define vvi vector<vector<int>>
#define vb vector<bool>
#define vpii vector<pii>
#define mii map<int,int>
#define dout(x) cout<<x<<' '<<#x<<endl;
#define vout(x) for(auto u : x)cout<<u<<' '; cout<<endl;
#define out(x) cout<<x<<endl;
#define out2(x,y) cout<<x<<' '<<y<<endl;
using namespace std;
const int mxn = 1e5 + 5;
map<int, vpii> adj;
int min_distance(vector<signed> x, vector<signed> h, vector<signed> l, vector<signed> r, vector<signed> y, signed s, signed g) {
	//encode a position as h * n + i
	int n = x.size();
	int m = l.size();
	vvi ints(n);
	f0r(i,m){
		for(int j = l[i]; j<=r[i]; j++){
			if(h[j] >= y[i])ints[j].pb(y[i] * n + j);
		}
		for(int j = l[i]; j<r[i]; j++){
			adj[y[i] * n + j].pb(mp(y[i] * n + j + 1, x[j+1] - x[j]));
			adj[y[i] * n + j + 1].pb(mp(y[i] * n + j, x[j+1] - x[j]));
		}
	}
	f0r(i,n){
		ints[i].pb(i);
	}
	f0r(i,n){
		sort(ints[i].begin(), ints[i].end());
	}
	f0r(i,n){
		f0r(j, ints[i].size() - 1){
			int h1 = ints[i][j] / n;
			int h2 = ints[i][j+1] / n;
			adj[ints[i][j]].pb(mp(ints[i][j+1], h2-h1));
			adj[ints[i][j+1]].pb(mp(ints[i][j], h2-h1));
		}
	}
	
	mii dist;
	dist[s] = 0;
	priority_queue<pii>q;
	q.push(mp(0,s));
	while(!q.empty()){
		int node = q.top().second;
		q.pop();
		for(auto u : adj[node]){
			int b = u.first;
			int w = u.second;
			if(!dist.count(b) || dist[b] > dist[node] + w){
				dist[b] = dist[node] + w;
				q.push(mp(-dist[b], b));
			}
		}
	}
	/*
	out(dist[n + 1]);
	out(dist[6 * n + 1]);
	out(dist[6 * n + 2]);
	out(dist[7*n+2]);
	out(dist[7*n+6]);
	out(dist[5*n+6]);
	out(dist[5*n+5]);
	*/
	if(!dist.count(g))return -1;
	else return dist[g];
	
	
	return 1;
}

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