Submission #899836

#	Time	Username	Problem	Language	Result	Execution time	Memory
899836		TAhmed33	Reconstruction Project (JOI22_reconstruction)	C++98	14 / 100	5017 ms	33456 KiB

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 / 3
• Subtask 2: 4 / 4
• Subtask 3: 7 / 7
• Subtask 4: 0 / 28
• Subtask 5: 0 / 35
• Subtask 6: 0 / 23