Submission #4334146


Source Code Expand

Copy
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"

using namespace std;

const long long int MOD = 1000000007;
//const int MOD = 998244353;

long long int N, M, K, H, W, L, R;
//int N, M, K, H, W, L, R

struct pyNode {
	long long int x, y, index;
	long long int cost;
	bool operator<(const pyNode& p)const {
		if (y < p.y)return true;
		if (y > p.y)return false;
		return x < p.x;
	}
};

struct pxNode {
	long long int x, y, index;
	long long int cost;
	bool operator<(const pxNode& p)const {
		if (x < p.x)return true;
		if (x > p.x)return false;
		return y < p.y;
	}
};

pyNode converter(pxNode n) {
	pyNode ret;
	ret.x = n.x;
	ret.y = n.y;
	ret.index = n.index;
	ret.cost = n.cost;
	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> L >> R;
	L--;
	R--;
	vector<pxNode>px(N);
	for (int i = 0; i < N; i++) {
		cin >> W >> H >> K;
		px[i] = { W,H,i,K };
	}
	if (px[R] < px[L])swap(L, R);
	int sy, sx, gy, gx,sc,gc;
	sx = px[L].x;
	sy = px[L].y;
	gx = px[R].x;
	gy = px[R].y;
	sc = px[L].cost;
	gc = px[R].cost;
	sort(px.begin(), px.end());
	map<pyNode, long long int>mp;
	long long int ans = MOD * MOD;
	for (int i = 0; i < N; i++) {
		auto it = mp.lower_bound(converter(px[i]));
		long long int cost = MOD * MOD;
		if (px[i].index == L)cost = 0;
		else if (px[i].x <= sx && px[i].y <= sy)cost = sc;
		else {
			if (it != mp.begin()) {
				cost = prev(it)->second + px[i].cost;
			}
		}
		if (px[i].index == R) {
			ans = min(ans,cost);
		}
		if (it == mp.begin() || prev(it)->second > cost) {
			mp[converter(px[i])] = cost;
			it = mp.lower_bound(converter(px[i]));
			while (next(it) != mp.end() && next(it)->second >= cost) mp.erase(next(it));
		}
		long long int add_cost = cost + px[i].cost;
		if (px[i].x >= gx && px[i].y >= gy)	ans = min(ans, add_cost);
		if (px[i].x <= gx && px[i].y <= gy)ans = min(ans, cost + gc);
		if (mp.begin()->second > add_cost) {
			auto fpx = mp.begin()->first;
			while (mp.begin()->second > add_cost)mp.erase(mp.begin());
			mp[fpx] = add_cost;
		}
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Submission Time
Task F - Flights
User olphe
Language C++14 (GCC 5.4.1)
Score 900
Code Size 2478 Byte
Status
Exec Time 65 ms
Memory 7040 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt
All 900 / 900 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
01-01.txt 1 ms 256 KB
01-02.txt 39 ms 3456 KB
01-03.txt 39 ms 3328 KB
01-04.txt 39 ms 3328 KB
01-05.txt 57 ms 5376 KB
01-06.txt 44 ms 3456 KB
01-07.txt 54 ms 4736 KB
01-08.txt 59 ms 5888 KB
01-09.txt 45 ms 3456 KB
01-10.txt 56 ms 4736 KB
01-11.txt 58 ms 5632 KB
01-12.txt 45 ms 3456 KB
01-13.txt 54 ms 4608 KB
01-14.txt 60 ms 5760 KB
01-15.txt 44 ms 3456 KB
01-16.txt 55 ms 4736 KB
01-17.txt 57 ms 5504 KB
01-18.txt 46 ms 3456 KB
01-19.txt 54 ms 4608 KB
01-20.txt 57 ms 5632 KB
01-21.txt 42 ms 3456 KB
01-22.txt 42 ms 3712 KB
01-23.txt 65 ms 7040 KB
sample-01.txt 1 ms 256 KB
sample-02.txt 1 ms 256 KB