Submission #1312377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312377		vlomaczk	Treatment Project (JOI20_treatment)	C++20	0 / 100	25 ms	5068 KiB

treatment

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n, m;
	cin >> n >> m;
	vector<int> T(m), L(m), R(m), C(m);
	for(int i=0; i<m; ++i) {
		cin >> T[i] >> L[i] >> R[i] >> C[i];
	}
	vector<vector<int>> g(m);
	vector<int> targets;
	ll inf = 1e18;
	vector<ll> dist(m, inf);
	auto check = [&](int i, int j) {
		if(T[i] >= T[j]) return (R[i] + 1 >= L[j] + T[i] - T[j]);
		return (R[i] + T[i] - T[j] + 1 >= L[j]);
	};
	for(int i=0; i<m; ++i) {
		if(L[i]==1) dist[i] = C[i];
		if(R[i]==n) targets.push_back(i);
	}
	priority_queue<pair<int, int>> pq;
	for(int i=0; i<m; ++i) if(dist[i] < inf) pq.push({-dist[i], i});
	while(pq.size()) {
		auto[dv, v] = pq.top();
		pq.pop(); dv*=-1;
		if(dv!=dist[v]) continue;
		for(int u=0; u<n; ++u) {
			if(!check(v,u)) continue;
			if(dist[u] > dist[v] + C[u]) {
				dist[u] = dist[v] + C[u];
				pq.push({-dist[u], u});
			}
		}
	}
	ll ans = inf;
	for(int x : targets) {
		ans = min(ans, dist[x]);
	}
	if(ans==inf) cout << "-1\n";
	else cout << ans << "\n";

	return 0;
}

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