Submission #587083

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
587083	2022-07-01T09:46:43 Z	8e7	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	1124 ms	28924 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	212 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	212 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1097 ms	15456 KB	Output is correct
5	Correct	1058 ms	26764 KB	Output is correct
6	Correct	1035 ms	26752 KB	Output is correct
7	Correct	952 ms	28508 KB	Output is correct
8	Correct	840 ms	28716 KB	Output is correct
9	Correct	898 ms	28872 KB	Output is correct
10	Correct	1124 ms	26812 KB	Output is correct
11	Correct	886 ms	28924 KB	Output is correct