Submission #219407

#	Time	Username	Problem	Language	Result	Execution time	Memory
219407		maruii	Treatment Project (JOI20_treatment)	C++14	0 / 100	3078 ms	3212 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);
	return a[1] - a[0] - 1 <= b[1] - b[0] && b[1] + b[0] <= a[2] + a[0] + 1 ||
	a[1] - a[0] - 1 <= b[2] - b[0] && b[2] + b[0] <= a[2] + a[0] + 1;
}

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;
}

Compilation message (stderr)

treatment.cpp: In function 'bool chk(tii, tii)':
treatment.cpp:23:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  return a[1] - a[0] - 1 <= b[1] - b[0] && b[1] + b[0] <= a[2] + a[0] + 1 ||

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