Submission #445691

#	Time	Username	Problem	Language	Result	Execution time	Memory
445691		nonsensenonsense1	Bridges (APIO19_bridges)	C++17	73 / 100	3074 ms	11180 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() {
		p = 0;
		size = 1;
	}
	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 = 500;
int n, m, q, a[M], b[M], w[M], t[M], x[M], y[M], ans[M], u[M], last[M], sum, vis[N];
std::vector<int> g[N];
dsu d[N];

void add_edge(int u, int v) 
{
	g[u].push_back(v);
	g[v].push_back(u);
}

void dfs(int v) 
{
	sum += d[v].size;
	for (int i = 0; i < g[v].size(); ++i) if (vis[g[v][i]] != vis[v]) {
		vis[g[v][i]] = vis[v];
		dfs(g[v][i]);
	}
}

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 = ask[j].second - 1; k >= i; --k) if (t[k] == 1 && last[x[k]] != ask[j].second + 1) {
				if (y[k] >= ask[j].first) add_edge(d[a[x[k]]].find() - d, d[b[x[k]]].find() - d);
				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) add_edge(d[a[x[k]]].find() - d, d[b[x[k]]].find() - d);
				last[x[k]] = ask[j].second + 1;
			}
			sum = 0;
			vis[d[x[ask[j].second]].find() - d] = ask[j].second + 1;
			dfs(d[x[ask[j].second]].find() - d);
			ans[ask[j].second] = sum;
			for (int k = std::min(q, i + K) - 1; k >= i; --k) if (t[k] == 1) {
				g[d[a[x[k]]].find() - d].resize(0);
				g[d[b[x[k]]].find() - d].resize(0);
			}
		}
		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 'void dfs(int)':
bridges.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for (int i = 0; i < g[v].size(); ++i) if (vis[g[v][i]] != vis[v]) {
      |                  ~~^~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%d%d%d", a + i, b + i, w + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
bridges.cpp:71:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |    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: 0 / 27