Submission #445719

#	Time	Username	Problem	Language	Result	Execution time	Memory
445719		nonsensenonsense1	Bridges (APIO19_bridges)	C++17	100 / 100	2890 ms	11964 KiB

bridges

#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
#include <set>

struct dsu {
	dsu *p;
	int size;
	dsu() {
		p = 0;
		size = 1;
	}
	void reset(int size_ = 1) {
		p = 0;
		size = size_;
	}
	dsu *find() {
		if (!p) return this;
		return p = p->find();
	}
};

void unite(dsu *a, dsu *b) 
{
	a = a->find();
	b = b->find();
	if (a != b) {
		if (a->size < b->size) std::swap(a, b);
		b->p = a;
		a->size += b->size;
	}
}

const int N = 50000;
const int M = 100000;
const int K = 1000;
int n, m, q, a[M], b[M], aa[M], bb[M], w[M], t[M], x[M], y[M], ans[M], u[M], last[M];
dsu d[N], dd[N];

int main() 
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; ++i) {
		scanf("%d%d%d", a + i, b + i, w + i);
		--a[i];
		--b[i];
	}
	scanf("%d", &q);
	for (int i = 0; i < q; i += K) {
		std::vector<std::pair<int, int> > ask;
		for (int j = i; j < std::min(q, i + K); ++j) {
			scanf("%d%d%d", t + j, x + j, y + j);
			--x[j];
			if (t[j] == 1) u[x[j]] = i + 1;
			else ask.push_back(std::make_pair(y[j], j));
		}
		std::sort(ask.begin(), ask.end());
		std::vector<std::pair<int, int> > s;
		for (int j = 0; j < m; ++j) if (u[j] <= i) s.push_back(std::make_pair(w[j], j));
		std::sort(s.begin(), s.end());
		int it = (int)s.size() - 1;
		for (int j = (int)ask.size() - 1; j >= 0; --j) {
			while (it >= 0 && s[it].first >= ask[j].first) {
				unite(d + a[s[it].second], d + b[s[it].second]);
				--it;
			}
			for (int k = std::min(q, i + K) - 1; k >= i; --k) if (t[k] == 1) {
				aa[k] = d[a[x[k]]].find() - d;
				bb[k] = d[b[x[k]]].find() - d;
				dd[aa[k]].reset(d[aa[k]].size);
				dd[bb[k]].reset(d[bb[k]].size);
			}
			dd[d[x[ask[j].second]].find() - d].reset(d[x[ask[j].second]].find()->size);
			for (int k = ask[j].second - 1; k >= i; --k) if (t[k] == 1 && last[x[k]] != ask[j].second + 1) {
				if (y[k] >= ask[j].first) unite(dd + aa[k], dd + bb[k]);
				last[x[k]] = ask[j].second + 1;
			}
			for (int k = std::min(q, i + K) - 1; k >= ask[j].second; --k) if (t[k] == 1 && last[x[k]] != ask[j].second + 1) {
				if (w[x[k]] >= ask[j].first) unite(dd + aa[k], dd + bb[k]);
				last[x[k]] = ask[j].second + 1;
			}
			ans[ask[j].second] = dd[d[x[ask[j].second]].find() - d].find()->size;
		}
		for (int j = i; j < std::min(q, i + K); ++j) if (t[j] == 1) w[x[j]] = y[j];
		for (int i = 0; i < n; ++i) d[i].reset();
	}
	for (int i = 0; i < q; ++i) if (ans[i]) printf("%d\n", ans[i]);
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%d%d%d", a + i, b + i, w + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
bridges.cpp:53:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |    scanf("%d%d%d", t + j, x + j, y + j);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27