Submission #587083

#	Time	Username	Problem	Language	Result	Execution time	Memory
587083		8e7	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	1124 ms	28924 KiB

reconstruction

//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
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 505
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;
struct edge{
	int u, v, w;
	edge(){u = v = w = 0;}
	edge(int a, int b, int c){u = a, v = b, w = c;}
};

vector<edge> ed;
vector<int> wei;
vector<int> pos[maxn];
int idx[maxn];
int n, m;

int main() {
	io
	cin >> n >> m;
	vector<pii> ev;
	for (int i = 0;i < m;i++) {
		int u, v, w;
		cin >> u >> v >> w;
		pos[u].push_back(w);
		
		ed.push_back(edge(u, v, w));
		wei.push_back(w);
	}
	sort(ed.begin(), ed.end(), [&] (edge x, edge y){return x.w < y.w;});
	sort(wei.begin(), wei.end());
	for (int i = 1;i <= n;i++) {
		sort(pos[i].begin(), pos[i].end());
		idx[i] = 0;
		for (int j = 1;j < pos[i].size();j++) {
			ev.push_back({(pos[i][j] + pos[i][j-1] + 1) / 2, i});
		}
	}
	sort(ev.begin(), ev.end());

	int q;
	cin >> q;

	int ind = 0;
	for (int i = 0;i < q;i++) {
		int x;
		cin >> x;
		while (ind < ev.size() && ev[ind].ff <= x) {
			idx[ev[ind].ss]++;
			ind++;
		}
		ll ans = 0;
		for (int j = 1;j < n;j++) {
			ans += abs(pos[j][idx[j]] - x);
		}
		cout << ans << "\n";	
	}
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for (int j = 1;j < pos[i].size();j++) {
      |                  ~~^~~~~~~~~~~~~~~
reconstruction.cpp:65:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   while (ind < ev.size() && ev[ind].ff <= x) {
      |          ~~~~^~~~~~~~~~~

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