Submission #445699

#	Time	Username	Problem	Language	Result	Execution time	Memory
445699		nonsensenonsense1	Bridges (APIO19_bridges)	C++17	44 / 100	3066 ms	10180 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 p = p->find();
		return this;
	}
};

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], w[M], t[M], x[M], y[M], ans[M], u[M], last[M], vis[N];
dsu d[N], dd[N];

void reset(int v) 
{
	dd[d[v].find() - d].reset(d[v].find()->size);
}

int main() 
{
	scanf("%d%d", &n, &m);
	std::set<std::pair<int, int> > s;
	for (int i = 0; i < m; ++i) {
		scanf("%d%d%d", a + i, b + i, w + i);
		--a[i];
		--b[i];
		s.insert(std::make_pair(w[i], 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::set<std::pair<int, int> >::iterator it = s.end();
		for (int j = (int)ask.size() - 1; j >= 0; --j) {
			while (it != s.begin() && prev(it)->first >= ask[j].first) {
				--it;
				if (u[it->second] <= i) unite(d + a[it->second], d + b[it->second]);
			}
			for (int k = std::min(q, i + K) - 1; k >= i; --k) if (t[k] == 1) {
				reset(a[x[k]]);
				reset(b[x[k]]);
			}
			reset(x[ask[j].second]);
			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(d[a[x[k]]].find() - d + dd, d[b[x[k]]].find() - d + dd);
				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(d[a[x[k]]].find() - d + dd, d[b[x[k]]].find() - d + dd);
				last[x[k]] = ask[j].second + 1;
			}
			vis[d[x[ask[j].second]].find() - d] = 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) {
			s.erase(std::make_pair(w[x[j]], x[j]));
			w[x[j]] = y[j];
			s.insert(std::make_pair(y[j], x[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:48:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%d%d%d", a + i, b + i, w + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
bridges.cpp:60:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |    scanf("%d%d%d", t + j, x + j, y + j);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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