Submission #779362

#	Time	Username	Problem	Language	Result	Execution time	Memory
779362		ymm	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	991 ms	31700 KiB

reconstruction

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 512;

namespace dsu {
	struct edge {
		int v, u, w;
		int nxt;
	} edges[(1<<27)/sizeof(edge)];

	int new_edge() {
		static int nxt = 1;
		return nxt++;
	}

	int st;

	void push(int v, int u, int w) {
		int e = new_edge();
		edges[e].v = v;
		edges[e].u = u;
		edges[e].w = w;
		edges[e].nxt = st;
		st = e;
	}

	int par[N];
	int sz[N];

	int rt(int v) { return par[v] == -1? v: rt(par[v]); }
	bool unite(int v, int u) {
		v = rt(v);
		u = rt(u);
		if (v == u)
			return 0;
		if (sz[v] < sz[u])
			swap(v, u);
		sz[v] += sz[u];
		par[u] = v;
		return 1;
	}

	int Do(int v, int u) {
		fill(par, par+N, -1);
		fill(sz, sz+N, 1);
		for (int *e = &st; *e;) {
			int x = edges[*e].v;
			int y = edges[*e].u;
			if (!unite(x, y)) {
				*e = edges[*e].nxt;
				continue;
			}
			v = rt(v);
			u = rt(u);
			if (v == u)
				return edges[*e].w;
			e = &edges[*e].nxt;
		}
		return -1;
	}
}

vector<pair<int,pii>> E;
vector<pii> ev;
int n, m;

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	Loop (i,0,m) {
		int v, u, w;
		cin >> v >> u >> w;
		--v; --u;
		E.push_back({w, {v, u}});
	}
	sort(E.begin(), E.end());
	Loop (i,0,E.size()) {
		auto [w, dard] = E[i];
		auto [v, u] = dard;
		int x = dsu::Do(v, u);
		if (x == -1) {
			ev.push_back({0, w});
			//cerr << w << ' ' << ev.back().first << '\n';
		} else if (x != w) {
			ev.push_back({(x+w+2)/2, w});
			//cerr << w << ' ' << ev.back().first << '\n';
		}
		dsu::push(v, u, w);
	}
	dsu::st = 0;
	for (int l = m, r = m; r > 0; r = l) {
		while (l > 0 && E[l-1].first == E[r-1].first)
			--l;
		Loop (i,l,r) {
			auto [w, dard] = E[i];
			auto [v, u] = dard;
			int x = dsu::Do(v, u);
			if (x != -1 && x != w) {
				ev.push_back({(x+w)/2+1, ~w});
				//cerr << w << ' ' << x << ' ' << ev.back().first << "-" << '\n';
			}
			dsu::push(v, u, w);
		}
	}
	sort(ev.begin(), ev.end());
	int p = 0;
	ll ans = 0;
	int q;
	cin >> q;
	multiset<int> Sr;
	ll suml = 0, sumr = 0;
	ll cntl = 0, cntr = 0;
	while (q--) {
		int x;
		cin >> x;
		multiset<int>::iterator it;
		while (Sr.size() && *(it = Sr.begin()) < x) {
			sumr -= *it;
			suml += *it;
			cntr--;
			cntl++;
			Sr.erase(it);
		}
		while (p < ev.size() && ev[p].first <= x) {
			int dard = ev[p++].second;
			if (dard < 0) {
				dard = ~dard;
				if (dard < x) {
					suml -= dard;
					cntl--;
				} else {
					sumr -= dard;
					cntr--;
					auto it = Sr.find(dard);
					assert(it != Sr.end());
					Sr.erase(it);
				}
			} else {
				if (dard < x) {
					suml += dard;
					cntl++;
				} else {
					sumr += dard;
					cntr++;
					Sr.insert(dard);
				}
			}
		}
		ll ans = (cntl*x - suml) + (sumr - cntr*x);
		//cerr << cntl << " " << suml << " - " << cntr << " " << sumr << '\n';
		cout << ans << '\n';
		//cerr << "Hi\n";
	}
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:131:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |   while (p < ev.size() && ev[p].first <= x) {
      |          ~~^~~~~~~~~~~
reconstruction.cpp:114:5: warning: unused variable 'ans' [-Wunused-variable]
  114 |  ll ans = 0;
      |     ^~~

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