Submission #811019

#	Time	Username	Problem	Language	Result	Execution time	Memory
811019		Username4132	Sky Walking (IOI19_walk)	C++14	0 / 100	113 ms	26192 KiB

walk

#include "walk.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second

struct node{
	int ind;
	ll cost;
	node(int _ind, ll _cost) : ind(_ind), cost(_cost) {}
};

bool operator<(node a, node b){
	return a.cost>b.cost;
}

const int MAXN = 100010;
const ll INF = 1000000000000000000;
int n, m;
ll dis[2*MAXN];
vector<pii> pts[MAXN];
vector<pii> gr[2*MAXN];

void dij(){
	priority_queue<node> Q;
	forn(i, 2*m + 2) dis[i] = INF;
	dis[2*m]=0;
	Q.push(node(2*m, 0));
	while(!Q.empty()){
		node v = Q.top();
		Q.pop();
		if(dis[v.ind]<v.cost) continue;
		for(pii to:gr[v.ind]){
			ll nc = v.cost + to.S;
			if(nc < dis[to.F]){
				dis[to.F] = nc;
				Q.push(node(to.F, nc));
			}
		}
	}
}


long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	n = (int)x.size();
	m = (int)l.size();

	forn(i, m){
		pts[l[i]].PB({y[i], i});
		pts[r[i]].PB({y[i], m+i});
		gr[i].PB({m+i, x[r[i]]-x[l[i]]});
		gr[m+i].PB({i, x[r[i]]-x[l[i]]});
	}

	pts[s].PB({0, 2*m});
	pts[g].PB({0, 2*m + 1});

	forn(i, n){
		sort(pts[i].begin(), pts[i].end());
		forn(j, (int)pts[i].size()-1){
			pii pt1 = pts[i][j], pt2 = pts[i][j+1];
			gr[pt1.S].PB({pt2.S, pt2.F - pt1.F});
			gr[pt2.S].PB({pt1.S, pt2.F - pt1.F});			
		}
	}

	dij();

	/*forn(i, 2*m+2){
		cerr << i << ": ";
		for(pii el:gr[i]) cerr << "(" << el.F << ", " << el.S << "), ";
		cerr << endl;
	}

	cerr << dis[0] << "!!" << endl;
	cerr << dis[1] << "!!" << endl;*/

	return dis[2*m+1]==INF? -1 : dis[2*m+1];
}

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