Submission #219411

#	Time	Username	Problem	Language	Result	Execution time	Memory
219411		maruii	Treatment Project (JOI20_treatment)	C++14	0 / 100	3083 ms	3188 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using tii = array<int, 3>;
using pil = pair<int, ll>;
#define ff first
#define ss second
#define eack emplace_back
#define all(x) (x).begin(), (x).end()

const ll INF = 1e18;
int N, M;
map<int, vector<pair<pii, int>>> MP;

using abc = pair<ll, tii>;
abc in[100005];
priority_queue<abc, vector<abc>, greater<abc>> pq;
map<tii, ll> dist;

bool chk(tii a, tii b) {
	if (a[0] > b[0]) swap(a, b);
	int l = b[1] - 1, r = b[2] + 1;
	int s = a[1], e = a[2];
	if (s > 1) s += b[0] - a[0];
	if (e < N) e -= b[0] - a[0];
	return l <= e && s <= r;
}

tii f(tii a, tii b) {
	if (a[0] > b[0]) swap(a, b);
	if (a[1] > 1) a[1] += b[0] - a[0];
	if (a[2] < N) a[2] -= b[0] - a[0];
	return {b[0], min(a[1], b[1]), max(a[2], b[2])};
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= M; ++i) {
		int t, l, r, c; cin >> t >> l >> r >> c;
		in[i] = {c, {t, l, r}};
		if (l == 1) {
			pq.push(in[i]);
			tii n = {t, l, r};
			if (!dist.count(n)) dist[n] = c;
			else dist[n] = min(dist[n], (ll)c);
		}
	}
	while (pq.size()) {
		auto x = pq.top(); pq.pop();
		ll c = x.ff;
		int t = x.ss[0], l = x.ss[1], r = x.ss[2];
		tii v = {t, l, r};
		if (r == N) return !printf("%lld", c);
		if (c > dist[v]) continue;
		for (int i = 1; i <= M; ++i) if (chk(v, in[i].ss)) {
			tii n = f(v, in[i].ss);
			if (n == v) continue;
			if (!dist.count(n) || dist[n] > c + in[i].ff) {
				dist[n] = c + in[i].ff;
				pq.emplace(c + in[i].ff, n);
			}
		}
	}
	cout << -1;
	return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 61