Submission #899836

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
899836	2024-01-07T07:03:13 Z	TAhmed33	Reconstruction Project (JOI22_reconstruction)	C++	14 / 100	5000 ms	33456 KB

reconstruction

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector <ll> adj[501][501];
const ll inf = 1e16;
int main () {
	int n, m;
	cin >> n >> m;
	bool flag = 1;
	for (int i = 1; i <= m; i++) {
		ll a, b, c;
		cin >> a >> b >> c;
		adj[a][b].push_back(c);
		adj[b][a].push_back(c);
		flag &= b == a + 1;
	}
	for (int i = 1; i < n; i++) {
		sort(adj[i + 1][i].begin(), adj[i + 1][i].end());
	}
	int ptr[n + 1] = {};
	int q;
	cin >> q;
	while (q--) {
		ll x;
		cin >> x;
		if (flag) {
			ll sum = 0;
			for (int i = 2; i <= n; i++) {
				while (ptr[i] + 1 < (int)adj[i][i - 1].size() && abs(adj[i][i - 1][ptr[i] + 1] - x) < abs(adj[i][i - 1][ptr[i]] - x)) ptr[i]++;
				sum += abs(x - adj[i][i - 1][ptr[i]]);
			}
			cout << sum << '\n';
		} else {
			ll dist[n + 1], vis[n + 1];
			for (int i = 0; i <= n; i++) {
				dist[i] = inf;
				vis[i] = 0;
			}
			ll sum = 0;
			dist[1] = 0; vis[1] = 1;
			for (int j = 2; j <= n; j++) {
				for (auto k : adj[1][j]) {
					dist[j] = min(dist[j], abs(k - x));
				}
			}
			for (int i = 2; i <= n; i++) {
				ll mn = 1 + inf, pos = -1;
				for (int j = 1; j <= n; j++) {
					if (!vis[j] && dist[j] < mn) {
						pos = j;
						mn = dist[j];
					}
				}
			//	for (int j = 1; j <= n; j++) cout << dist[j] << " ";
				//cout << '\n';
				vis[pos] = 1;
				sum += dist[pos];
				for (int j = 1; j <= n; j++) {
					if (vis[j]) continue;
					for (auto k : adj[pos][j]) {
						dist[j] = min(dist[j], abs(k - x));
					}
				}
			}
			//cout << '\n';
			cout << sum << '\n';
		}
	}
}

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6236 KB	Output is correct
2	Correct	2 ms	6236 KB	Output is correct
3	Correct	2 ms	6236 KB	Output is correct
4	Correct	2 ms	6236 KB	Output is correct
5	Correct	2 ms	6236 KB	Output is correct
6	Correct	2 ms	6236 KB	Output is correct
7	Correct	2 ms	6328 KB	Output is correct
8	Correct	2 ms	6236 KB	Output is correct
9	Correct	2 ms	6236 KB	Output is correct
10	Correct	2 ms	6236 KB	Output is correct
11	Correct	2 ms	6248 KB	Output is correct
12	Correct	2 ms	6236 KB	Output is correct
13	Correct	3 ms	6236 KB	Output is correct
14	Correct	3 ms	6232 KB	Output is correct
15	Correct	2 ms	6236 KB	Output is correct
16	Correct	2 ms	6236 KB	Output is correct
17	Correct	2 ms	6236 KB	Output is correct
18	Correct	2 ms	6236 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6236 KB	Output is correct
2	Correct	2 ms	6236 KB	Output is correct
3	Correct	2 ms	6236 KB	Output is correct
4	Correct	2 ms	6236 KB	Output is correct
5	Correct	2 ms	6236 KB	Output is correct
6	Correct	2 ms	6236 KB	Output is correct
7	Correct	2 ms	6328 KB	Output is correct
8	Correct	2 ms	6236 KB	Output is correct
9	Correct	2 ms	6236 KB	Output is correct
10	Correct	2 ms	6236 KB	Output is correct
11	Correct	2 ms	6248 KB	Output is correct
12	Correct	2 ms	6236 KB	Output is correct
13	Correct	3 ms	6236 KB	Output is correct
14	Correct	3 ms	6232 KB	Output is correct
15	Correct	2 ms	6236 KB	Output is correct
16	Correct	2 ms	6236 KB	Output is correct
17	Correct	2 ms	6236 KB	Output is correct
18	Correct	2 ms	6236 KB	Output is correct
19	Correct	3 ms	6336 KB	Output is correct
20	Correct	87 ms	11608 KB	Output is correct
21	Correct	67 ms	9552 KB	Output is correct
22	Correct	76 ms	9824 KB	Output is correct
23	Correct	74 ms	9808 KB	Output is correct
24	Correct	77 ms	10328 KB	Output is correct
25	Correct	88 ms	11348 KB	Output is correct
26	Correct	127 ms	11728 KB	Output is correct
27	Correct	98 ms	11816 KB	Output is correct
28	Correct	88 ms	11600 KB	Output is correct
29	Correct	79 ms	11600 KB	Output is correct
30	Correct	92 ms	11652 KB	Output is correct
31	Correct	98 ms	11612 KB	Output is correct
32	Correct	112 ms	11788 KB	Output is correct
33	Correct	104 ms	11708 KB	Output is correct
34	Correct	82 ms	13648 KB	Output is correct
35	Correct	96 ms	11840 KB	Output is correct

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6236 KB	Output is correct
2	Correct	2 ms	6236 KB	Output is correct
3	Correct	2 ms	6236 KB	Output is correct
4	Correct	3657 ms	27632 KB	Output is correct
5	Correct	3532 ms	31120 KB	Output is correct
6	Correct	3614 ms	30976 KB	Output is correct
7	Correct	2748 ms	32844 KB	Output is correct
8	Correct	2714 ms	33456 KB	Output is correct
9	Correct	2619 ms	32460 KB	Output is correct
10	Correct	3500 ms	31316 KB	Output is correct
11	Correct	2697 ms	33164 KB	Output is correct

Subtask #4
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6236 KB	Output is correct
2	Correct	2 ms	6236 KB	Output is correct
3	Correct	2 ms	6236 KB	Output is correct
4	Correct	2 ms	6236 KB	Output is correct
5	Correct	2 ms	6236 KB	Output is correct
6	Correct	2 ms	6236 KB	Output is correct
7	Correct	2 ms	6328 KB	Output is correct
8	Correct	2 ms	6236 KB	Output is correct
9	Correct	2 ms	6236 KB	Output is correct
10	Correct	2 ms	6236 KB	Output is correct
11	Correct	2 ms	6248 KB	Output is correct
12	Correct	2 ms	6236 KB	Output is correct
13	Correct	3 ms	6236 KB	Output is correct
14	Correct	3 ms	6232 KB	Output is correct
15	Correct	2 ms	6236 KB	Output is correct
16	Correct	2 ms	6236 KB	Output is correct
17	Correct	2 ms	6236 KB	Output is correct
18	Correct	2 ms	6236 KB	Output is correct
19	Correct	2 ms	6232 KB	Output is correct
20	Execution timed out	5017 ms	7056 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

Subtask #5
0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6236 KB	Output is correct
2	Correct	2 ms	6236 KB	Output is correct
3	Correct	2 ms	6236 KB	Output is correct
4	Correct	2 ms	6236 KB	Output is correct
5	Correct	2 ms	6236 KB	Output is correct
6	Correct	2 ms	6236 KB	Output is correct
7	Correct	2 ms	6328 KB	Output is correct
8	Correct	2 ms	6236 KB	Output is correct
9	Correct	2 ms	6236 KB	Output is correct
10	Correct	2 ms	6236 KB	Output is correct
11	Correct	2 ms	6248 KB	Output is correct
12	Correct	2 ms	6236 KB	Output is correct
13	Correct	3 ms	6236 KB	Output is correct
14	Correct	3 ms	6232 KB	Output is correct
15	Correct	2 ms	6236 KB	Output is correct
16	Correct	2 ms	6236 KB	Output is correct
17	Correct	2 ms	6236 KB	Output is correct
18	Correct	2 ms	6236 KB	Output is correct
19	Correct	3 ms	6336 KB	Output is correct
20	Correct	87 ms	11608 KB	Output is correct
21	Correct	67 ms	9552 KB	Output is correct
22	Correct	76 ms	9824 KB	Output is correct
23	Correct	74 ms	9808 KB	Output is correct
24	Correct	77 ms	10328 KB	Output is correct
25	Correct	88 ms	11348 KB	Output is correct
26	Correct	127 ms	11728 KB	Output is correct
27	Correct	98 ms	11816 KB	Output is correct
28	Correct	88 ms	11600 KB	Output is correct
29	Correct	79 ms	11600 KB	Output is correct
30	Correct	92 ms	11652 KB	Output is correct
31	Correct	98 ms	11612 KB	Output is correct
32	Correct	112 ms	11788 KB	Output is correct
33	Correct	104 ms	11708 KB	Output is correct
34	Correct	82 ms	13648 KB	Output is correct
35	Correct	96 ms	11840 KB	Output is correct
36	Execution timed out	5014 ms	12120 KB	Time limit exceeded
37	Halted	0 ms	0 KB	-

Subtask #6
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6236 KB	Output is correct
2	Correct	2 ms	6236 KB	Output is correct
3	Correct	2 ms	6236 KB	Output is correct
4	Correct	2 ms	6236 KB	Output is correct
5	Correct	2 ms	6236 KB	Output is correct
6	Correct	2 ms	6236 KB	Output is correct
7	Correct	2 ms	6328 KB	Output is correct
8	Correct	2 ms	6236 KB	Output is correct
9	Correct	2 ms	6236 KB	Output is correct
10	Correct	2 ms	6236 KB	Output is correct
11	Correct	2 ms	6248 KB	Output is correct
12	Correct	2 ms	6236 KB	Output is correct
13	Correct	3 ms	6236 KB	Output is correct
14	Correct	3 ms	6232 KB	Output is correct
15	Correct	2 ms	6236 KB	Output is correct
16	Correct	2 ms	6236 KB	Output is correct
17	Correct	2 ms	6236 KB	Output is correct
18	Correct	2 ms	6236 KB	Output is correct
19	Correct	3 ms	6336 KB	Output is correct
20	Correct	87 ms	11608 KB	Output is correct
21	Correct	67 ms	9552 KB	Output is correct
22	Correct	76 ms	9824 KB	Output is correct
23	Correct	74 ms	9808 KB	Output is correct
24	Correct	77 ms	10328 KB	Output is correct
25	Correct	88 ms	11348 KB	Output is correct
26	Correct	127 ms	11728 KB	Output is correct
27	Correct	98 ms	11816 KB	Output is correct
28	Correct	88 ms	11600 KB	Output is correct
29	Correct	79 ms	11600 KB	Output is correct
30	Correct	92 ms	11652 KB	Output is correct
31	Correct	98 ms	11612 KB	Output is correct
32	Correct	112 ms	11788 KB	Output is correct
33	Correct	104 ms	11708 KB	Output is correct
34	Correct	82 ms	13648 KB	Output is correct
35	Correct	96 ms	11840 KB	Output is correct
36	Correct	2 ms	6236 KB	Output is correct
37	Correct	2 ms	6236 KB	Output is correct
38	Correct	2 ms	6236 KB	Output is correct
39	Correct	3657 ms	27632 KB	Output is correct
40	Correct	3532 ms	31120 KB	Output is correct
41	Correct	3614 ms	30976 KB	Output is correct
42	Correct	2748 ms	32844 KB	Output is correct
43	Correct	2714 ms	33456 KB	Output is correct
44	Correct	2619 ms	32460 KB	Output is correct
45	Correct	3500 ms	31316 KB	Output is correct
46	Correct	2697 ms	33164 KB	Output is correct
47	Correct	2 ms	6232 KB	Output is correct
48	Execution timed out	5017 ms	7056 KB	Time limit exceeded
49	Halted	0 ms	0 KB	-

Submission #899836

Compilation message

Subtask #1 3.0 / 3.0

Subtask #2 4.0 / 4.0

Subtask #3 7.0 / 7.0

Subtask #4 0 / 28.0

Subtask #5 0 / 35.0

Subtask #6 0 / 23.0

Subtask #1
3.0 / 3.0

Subtask #2
4.0 / 4.0

Subtask #3
7.0 / 7.0

Subtask #4
0 / 28.0

Subtask #5
0 / 35.0

Subtask #6
0 / 23.0