Submission #544511

#	Time	Username	Problem	Language	Result	Execution time	Memory
544511		model_code	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	1948 ms	18400 KiB

reconstruction

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

struct UnionFind {
	int n;
	std::vector<int> a;
	UnionFind (int n) : n(n), a(n, -1) {}
	int root(int i) { return a[i] < 0 ? i : a[i] = root(a[i]); }
	bool unite(int x, int y) {
		x = root(x);
		y = root(y);
		if (x == y) return false;
		if (a[x] > a[y]) std::swap(x, y);
		a[x] += a[y];
		a[y] = x;
		return true;
	}
	bool same(int x, int y) { return root(x) == root(y); }
};

int main() {
	int n = ri();
	int m = ri();
	struct Hen {
		int a;
		int b;
		int c;
	};
	std::vector<Hen> hens(m);
	for (auto &i : hens) i.a = ri() - 1, i.b = ri() - 1, i.c = ri();
	
	std::sort(hens.begin(), hens.end(), [] (auto &i, auto &j) { return i.c < j.c; });
	
	// if the overall cost is ax + b, `add` is a list of
	//    {the value of x where the change occurs, {the change in a, the change in b}}
	std::vector<std::pair<int, std::pair<int, int> > > add;
	for (int i = 0; i < m; i++) {
		int cur_cost = hens[i].c;
		
		UnionFind uni(n);
		int j;
		for (j = i + 1; j < m; j++) {
			uni.unite(hens[j].a, hens[j].b);
			if (uni.same(hens[i].a, hens[i].b)) break;
		}
		int r = j;
		int r_value = r == m ? 1000000001 : cur_cost + (hens[r].c - cur_cost + 1) / 2;
		
		uni = UnionFind(n);
		for (j = i - 1; j >= 0; j--) {
			uni.unite(hens[j].a, hens[j].b);
			if (uni.same(hens[i].a, hens[i].b)) break;
		}
		int l = j;
		int l_value = l == -1 ? -1 : cur_cost - (cur_cost - hens[l].c) / 2;
		
		add.push_back({l_value, {-1, hens[i].c}}); // edge starting to be used (cost : 0 -> (hens[i].c - x))
		add.push_back({cur_cost, {2, -2 * hens[i].c}}); // at x == cur_cost (cost : (hens[i].c - x) -> (x - hens[i].c))
		add.push_back({r_value, {-1, hens[i].c}}); // edge ceasing to be used (cost : (x - hens[i].c) -> 0)
	}
	std::sort(add.begin(), add.end());
	
	size_t head = 0;
	int coeff = 0;
	int64_t constant = 0;
	int q = ri();
	for (int i = 0; i < q; i++) {
		int x = ri();
		
		while (head < add.size() && add[head].first <= x) {
			coeff += add[head].second.first;
			constant += add[head].second.second;
			head++;
		}
		
		printf("%" PRId64 "\n", constant + (int64_t) x * coeff);
	}
	
	return 0;
}

Compilation message (stderr)

reconstruction.cpp: In function 'int ri()':
reconstruction.cpp:5:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~

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