oj.uz

Submission #537973

# Submission time Handle Problem Language Result Execution time Memory
537973 2022-03-16T01:17:24 Z 8e7 Treatment Project (JOI20_treatment) C++17
35 / 100
 217 ms 25292 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 5005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1LL<<60;
bool adj[maxn][maxn], mark[maxn];
bool vis[maxn];
void dfs(int n, int tot) {
	vis[n] = 1;
	for (int v = 1;v <= tot;v++) {
		if (adj[n][v] && mark[v] && !vis[v]) {
			dfs(v, tot);
		}
	}
}
struct rect{
	int t, l, r;
	int cost;	
	rect(){t = l = r = cost = 0;}
} a[maxn];
ll dis[maxn];
int main() {
	io
	int L, n;
	cin >> L >> n;
	for (int i = 1;i <= n;i++) {
		cin >> a[i].t >> a[i].l >> a[i].r >> a[i].cost;	
		if (a[i].l == 1) adj[0][i] = 1;
		if (a[i].r == L) adj[i][n+1] = 1;
	}
	for (int i = 1;i <= n;i++) {
		dis[i] = inf;
		for (int j = 1;j <= n;j++) {
			if (i == j) continue;
			if (a[j].l <= a[i].r - abs(a[i].t - a[j].t) + 1) adj[i][j] = 1;	
		}
	}
	for (int i = 0;i <= n + 1;i++) {
		pary(adj[i], adj[i] + n + 2);
	}
	dis[n+1] = inf;

	priority_queue<pii, vector<pii>, greater<pii> > pq;	
	pq.push({0, 0});	
	while (pq.size()) {
		auto [d, cur] = pq.top();
		pq.pop();
		if (d != dis[cur]) continue;
		debug(cur, d);
		for (int i = 1;i <= n + 1;i++) {
			if (adj[cur][i] && d + a[i].cost < dis[i]) {
				dis[i] = d + a[i].cost;
				pq.push({dis[i], i});
			}
		}
	}
	cout << (dis[n+1] == inf ? -1 : dis[n+1]) << "\n";
}
/*
1000000000 16
6 2 2 1
4 999999997 999999999 4
2 999999997 1000000000 2
3 1 4 3
3 999999997 1000000000 3
5 999999998 999999999 3
6 999999999 999999999 1
2 1 4 2
6 3 999999998 1
999999987 1 1000000000 10
999999986 1 1000000000 10
999999985 1 1000000000 10
4 2 4 4
5 2 3 3
1 999999997 1000000000 1
1 1 4 1
*/

Compilation message

treatment.cpp: In function 'int main()':
treatment.cpp:13:19: warning: statement has no effect [-Wunused-value]
   13 | #define pary(...) 0
      |                   ^
treatment.cpp:55:3: note: in expansion of macro 'pary'
   55 |   pary(adj[i], adj[i] + n + 2);
      |   ^~~~
treatment.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
treatment.cpp:65:3: note: in expansion of macro 'debug'
   65 |   debug(cur, d);
      |   ^~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 4044 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 412 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 408 KB Output is correct
7 Correct 1 ms 412 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 412 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 408 KB Output is correct
20 Correct 160 ms 25164 KB Output is correct
21 Correct 165 ms 25132 KB Output is correct
22 Correct 63 ms 24972 KB Output is correct
23 Correct 59 ms 25036 KB Output is correct
24 Correct 116 ms 25116 KB Output is correct
25 Correct 76 ms 25120 KB Output is correct
26 Correct 64 ms 24776 KB Output is correct
27 Correct 62 ms 24240 KB Output is correct
28 Correct 117 ms 25236 KB Output is correct
29 Correct 72 ms 25068 KB Output is correct
30 Correct 47 ms 24984 KB Output is correct
31 Correct 44 ms 24256 KB Output is correct
32 Correct 217 ms 25244 KB Output is correct
33 Correct 119 ms 25292 KB Output is correct
34 Correct 151 ms 25092 KB Output is correct
35 Correct 217 ms 25160 KB Output is correct
36 Correct 121 ms 25176 KB Output is correct
37 Correct 149 ms 24936 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 4044 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -