Submission #587899

#	Time	Username	Problem	Language	Result	Execution time	Memory
587899		8e7	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	3760 ms	33624 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 maxm 100005
#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, id;
	edge(){u = v = w = id = 0;}
	edge(int a, int b, int c, int d){u = a, v = b, w = c, id = d;}
};
vector<int> wei;

inline void del(vector<pii> &v, pii x) {
	v.erase(find(v.begin(), v.end(), x));
}
inline void del(vector<int> &v, int x) {
	v.erase(find(v.begin(), v.end(), x));
}

vector<pii> ev;
vector<pii> adj[maxn];
pii best;
int bid = -1, t = 0;
bool getpath(int n, int par, int goal) {
	if (n == goal) return 1;
	for (auto [v, id]:adj[n]) {
		if (v != par && getpath(v, n, goal)) {
			if (id < bid) {
				bid = id;
				best = {n, v};
			}
			return 1;
		}
	}
	return 0;
}
void upd(edge e) {
	int u = e.u, v = e.v, w = e.w, id = e.id;
	bid = inf;
	if (u > v) swap(u, v);
	if (getpath(u, 0, v)) {
		if (best.ff > best.ss) swap(best.ff, best.ss);	
		del(adj[best.ff], make_pair(best.ss, bid));
		del(adj[best.ss], make_pair(best.ff, bid));
		ev.push_back({(wei[bid] + w + 1) / 2, bid});	
		ev.push_back({(wei[bid] + w + 1) / 2, id});	
	} else {
		ev.push_back({0, id});
	}
	adj[u].push_back({v, t});
	adj[v].push_back({u, t});
	t++;
}
bool on[maxm];
int main() {
	io
	int n, m;
	cin >> n >> m;
	vector<edge> ed;
	for (int i = 0;i < m;i++) {
		int u, v, w;
		cin >> u >> v >> w;
		ed.push_back(edge(u, v, w, i));	
	}
	sort(ed.begin(), ed.end(), [&] (edge x, edge y){return x.w < y.w;});
	for (int i = 0;i < m;i++) wei.push_back(ed[i].w), ed[i].id = i;
	for (int i = 0;i < m;i++) upd(ed[i]);
	sort(ev.begin(), ev.end());

	multiset<int> se;
	int q;
	cin >> q;
	vector<int> que(q);
	int ind = 0;
	for (int i = 0;i < q;i++) {
		cin >> que[i];
		while (ind < ev.size() && ev[ind].ff <= que[i]) {
			if (!on[ev[ind].ss]) {
				se.insert(wei[ev[ind].ss]);
				on[ev[ind].ss] = 1;
			} else {
				se.erase(se.find(wei[ev[ind].ss]));
			}
			ind++;
		}
		ll ans = 0;
		for (int j:se) ans += abs(j - que[i]);
		cout << ans << "\n";
	}
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:95: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]
   95 |   while (ind < ev.size() && ev[ind].ff <= que[i]) {
      |          ~~~~^~~~~~~~~~~

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