oj.uz

Submission #896697

# Submission time Handle Problem Language Result Execution time Memory
896697 2024-01-01T21:47:57 Z guechotjrhh Treatment Project (JOI20_treatment) C++14
35 / 100
 701 ms 524288 KB 
#include <iostream>
#include<vector>
#include<set>
#include<map>
#include<fstream>
#include<algorithm>
using namespace std;
#define ll long long
#define pi pair<ll,ll>
#define x first
#define y second
#define vi vector<int>
#define all(v) v.begin(),v.end()
#define l x.x
#define r x.y
#define t y.x
#define p y.y

ll min(ll a, ll b) { return a < b ? a : b; }
ll ab(ll n) { return n > 0 ? n : -n; }
int s, n;
long long func(int S, int N, vector<int> T, vector<int> L, vector<int> R, vector<int> P) {
	s = S; n = N;
	//N <= 5000
	vector<pair<pi, pi>> vec(n);
	for (int i = 0; i < n; i++)	vec[i] = { {L[i],R[i]}, {T[i],P[i]} };
	vector<pi> so(n);
	for (int i = 0; i < n; i++) {
		so[i] = {L[i] - T[i], i};
		if (L[i] == 1) so[i].x = -1e18;
	}
	sort(all(so));
	vector<ll> dp(n, 1e18);
	ll mn = 1e18;
	vector<vector<pi>> g(n + 2);
	for (int q = n - 1; q >= 0; q--) {
		int i = so[q].y;
		for (int z = 0; z < n; z++) {
			int j = so[z].y;
			if (R[i] - ab(T[j] - T[i]) >= L[j] - 1) {
				//dp[i] = min(dp[i], P[i] + dp[j]);
				//cout << q << ' ' << z << endl;
				g[i].push_back({ j, P[j] });
			}
		}
	}
	for (int i = 0; i < n; i++) if (L[i] == 1) g[n].push_back({ i,P[i] });
	for (int i = 0; i < n; i++) if (R[i] == s) g[i].push_back({ n+1,0 });

	vector<ll> dist(n + 2, 1e18);
	dist[n] = 0;
	set<pair<ll, int>> st;
	for (int i = 0; i < n+2; i++) st.insert({ dist[i],i });
	while (st.size()) {
		auto it = st.begin();
		int i = it->y;
		ll dst = it->x;
		st.erase(it);
		for (pi& pr : g[i]) {
			if (dist[pr.x] > pr.y + dst) {
				st.erase(st.find({ dist[pr.x],pr.x }));
				dist[pr.x] = pr.y + dst;
				st.insert({ dist[pr.x],pr.x });
			}
		}
	}
	return dist[n + 1] == 1e18 ? -1 : dist[n + 1];

	/*for (int q = n - 1; q >= 0; q--) {
		int i = so[q].y;
		if (R[i] == s) { dp[i] = P[i]; }
		else {
			for (int z = q + 1; z < n; z++) {
				int j = so[z].y;
				if (R[i]-ab(T[j]-T[i]) >= L[j]-1) {
					dp[i] = min(dp[i], P[i] + dp[j]);
				}
			}
		}
		cout << i << endl;
		cout << T[i] << ' ' << P[i] << endl;
		cout << L[i] << ' ' << R[i] << endl;
		cout << dp[i] << endl;
		if (L[i] == 1) mn = min(mn, dp[i]);
	}
	return mn == 1e18 ? -1 : mn;
	/*map<int, ll> mp;
	vector<pair<pi, pi>> vec(n);
	for (int i = 0; i < n; i++)	vec[i] = { {L[i],R[i]}, {T[i],P[i]} };
	sort(all(vec));
	mp[s + 1] = 0;
	for (int i = n - 1; i >= 0; i--) {
		auto it = mp.upper_bound(vec[i].r + 1);
		if (it != mp.begin()) {
			it--;
			if (mp.find(vec[i].l) == mp.end()) mp[vec[i].l] = vec[i].p + it->y;
			else mp[vec[i].l] = min(mp[vec[i].l], vec[i].p + it->y);

			auto it = mp.find(vec[i].l);
			while (next(it) != mp.end() && it->y < next(it)->y) mp.erase(next(it));
		}
	}
	if (mp.find(1) != mp.end()) return mp[1];
	return -1;*/
}

void run_tests() {
	string name = "03-00.txt";
	for (int i = 1; i <= 18; i++) {
		name[3] = '0' + i / 10;
		name[4] = '0' + i % 10;
		ifstream fin("in/" + name);
		ifstream fout("out/" + name);

		int S, N;
		fin >> S >> N;

		vector<int> T(N), L(N), R(N), P(N);
		for (int i = 0; i < N; i++) fin >> T[i] >> L[i] >> R[i] >> P[i];

		ll u = func(S, N, T, L, R, P),u1;
		fout >> u1;
		if (u != u1) {
			cout << i << endl;
			cout << S << ' ' << N << endl;
			cout << u << ' ' << u1 << endl;
			//for (int i = 0; i < N; i++) cout << T[i] << ' ' << L[i] << ' ' << R[i] << ' ' << P[i] << endl;
			return;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	//run_tests();
	//return 0;

	int S, N;
	cin >> S >> N;
	
	vector<int> T(N), L(N), R(N), P(N);
	for (int i = 0; i < N; i++) cin >> T[i] >> L[i] >> R[i] >> P[i];

	cout << func(S, N, move(T), move(L), move(R), move(P)) << endl;

	return 0;
}
/*
10 5
2 5 10 3
1 1 6 5
5 2 8 3
7 6 10 4
4 1 3 1

7
*/

Compilation message

treatment.cpp:87:2: warning: "/*" within comment [-Wcomment]
   87 |  /*map<int, ll> mp;
      |   
treatment.cpp: In function 'long long int func(int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
treatment.cpp:34:5: warning: unused variable 'mn' [-Wunused-variable]
   34 |  ll mn = 1e18;
      |     ^~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 701 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 856 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 456 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 856 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 456 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 268 ms 236636 KB Output is correct
21 Correct 271 ms 236864 KB Output is correct
22 Correct 53 ms 6484 KB Output is correct
23 Correct 67 ms 6484 KB Output is correct
24 Correct 218 ms 169832 KB Output is correct
25 Correct 165 ms 120392 KB Output is correct
26 Correct 143 ms 114512 KB Output is correct
27 Correct 178 ms 147208 KB Output is correct
28 Correct 203 ms 167880 KB Output is correct
29 Correct 160 ms 118336 KB Output is correct
30 Correct 161 ms 134480 KB Output is correct
31 Correct 181 ms 147020 KB Output is correct
32 Correct 270 ms 225888 KB Output is correct
33 Correct 386 ms 349796 KB Output is correct
34 Correct 251 ms 212304 KB Output is correct
35 Correct 272 ms 226444 KB Output is correct
36 Correct 384 ms 350312 KB Output is correct
37 Correct 261 ms 212116 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 701 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -