Submission #1127854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127854		Pwo	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	663 ms	17320 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, m, q, a[505];
vector<int> g[505];
vector<pair<int, pair<int, int>>> events;

int32_t main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v, w; cin >> u >> v >> w;
		if (u > v) swap(u, v);
		g[u].push_back(w);
	}
	
	for (int i = 1; i < n; i++) {
		sort(g[i].begin(), g[i].end());
		events.push_back({0, {i, g[i][0]}});
		for (size_t j = 1; j < g[i].size(); j++) {
			int idx = g[i][j - 1] + (g[i][j] - g[i][j - 1] + 1) / 2;
			events.push_back({idx, {i, g[i][j]}});
		}
	}

	sort(events.begin(), events.end());
	cin >> q; int ptr = 0;
	for (int i = 0; i < q; i++) {
		int x; cin >> x;
		while (ptr < (int) events.size() && events[ptr].first <= x) {
			a[events[ptr].second.first] = events[ptr].second.second;
			ptr++;
		}
		int cost = 0;
		for (int i = 1; i < n; i++) cost += abs(x - a[i]);
		cout << cost << '\n';
	}
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 4
• Subtask 3: 7 / 7
• Subtask 4: 0 / 28
• Subtask 5: 0 / 35
• Subtask 6: 0 / 23