Submission #402700

#	Time	Username	Problem	Language	Result	Execution time	Memory
402700		atoiz	Bridges (APIO19_bridges)	C++14	100 / 100	2953 ms	7796 KiB

bridges

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <cassert>
#include <numeric>

using namespace std;

const int N = 50007, M = 100007, Q = 100007, K = 300;
int n, sm, m, sq, q;
struct bridge_t { int u, v, st, en, d; } bridges[M + Q], candidates[K * 3 + 100];
struct query_t { int t, a, b, res; } queries[Q];
struct edge_t { int to, nxt; } edges[K * 6 + 100];
int head[K * 6 + 100], dsu[N], mapping[N], cnt[K * 6 + 100], stk[K * 6 + 100];
bool vis[K * 6 + 100];
bool in_mst[M + Q];

int root(int u) { return dsu[u] < 0 ? u : dsu[u] = root(dsu[u]); }
bool same(int u, int v) { return root(u) == root(v); }
void join(int u, int v) {
	u = root(u), v = root(v);
	if (u == v) return;
	if (dsu[u] > dsu[v]) swap(u, v);
	dsu[u] += dsu[v], dsu[v] = u;
}
int get_cnt(int u) { return -dsu[root(u)]; }

void solve(int qs, int qe) {
	memset(in_mst, 0, sizeof(in_mst[0]) * (m + 1));
	int c = 0, st = queries[qs].t, en = queries[qe - 1].t + 1;

	memset(dsu, -1, sizeof(dsu[0]) * (n + 1));
	for (int i = 1; i <= m; ++i) {
		bridge_t b = bridges[i];
		if (en <= b.st || b.en <= st) continue;
		if (not same(b.u, b.v)) {
			join(b.u, b.v);
			if (b.st <= st && en <= b.en) {
				in_mst[i] = true;
			}
		}
	}

	memset(dsu, -1, sizeof(dsu[0]) * (n + 1));
	for (int i = 1; i <= m; ++i) {
		bridge_t b = bridges[i];
		// int pc = c;
		if (en <= b.st || b.en <= st) continue;
		if (not same(b.u, b.v)) {
			if (b.st > st || en > b.en) {
				candidates[++c] = b;
			} else {
				join(b.u, b.v);
				if (!in_mst[i]) {
					candidates[++c] = b;
				}
			}
		}
		// cout << b.u << ' ' << b.v << ' ' << b.st << ' ' << b.en << ' ' << b.d << ": ";
		// if (pc < c) cout << 'c';
		// else if (in_mst[i]) cout << "i";
		// else cout << "-";
		// cout << endl;
	}

	vector<int> qis(qe - qs);
	iota(qis.begin(), qis.end(), qs);
	sort(qis.begin(), qis.end(), [&](int qi, int qj) {
		return queries[qi].b > queries[qj].b;
	});

	memset(dsu, -1, sizeof(dsu[0]) * (n + 1));
	int bi = 1;
	for (int qi : qis) {
		query_t &curq = queries[qi];
		for (; bi <= m && bridges[bi].d >= curq.b; ++bi) {
			if (in_mst[bi]) {
				join(bridges[bi].u, bridges[bi].v);
			}
		}

		int nv = 0, ne = 0;
		// cout << "q " << curq.t << ' ' << curq.a << ' ' << curq.b << " -> " << curq.res << endl;
		for (int ci = 1; ci <= c && candidates[ci].d >= curq.b; ++ci) {
			if (curq.t < candidates[ci].st || candidates[ci].en <= curq.t) continue;
			int u = root(candidates[ci].u), v = root(candidates[ci].v);
			if (u == v) continue;
			if (!mapping[u]) mapping[u] = ++nv, head[nv] = 0, vis[nv] = false, cnt[nv] = get_cnt(u);
			if (!mapping[v]) mapping[v] = ++nv, head[nv] = 0, vis[nv] = false, cnt[nv] = get_cnt(v);
			u = mapping[u], v = mapping[v];

			edges[++ne] = {v, head[u]}, head[u] = ne;
			edges[++ne] = {u, head[v]}, head[v] = ne;
		}

		// for (int u = 1; u <= n; ++u) cout << mapping[u] << ' '; cout << endl;
		int ns = 0;
		stk[++ns] = mapping[root(curq.a)];
		if (stk[ns]) {
			vis[stk[ns]] = true;

			while (ns) {
				int u = stk[ns--];
				// cout << u << ": " << cnt[u] << endl;
				curq.res += cnt[u];
				for (int i = head[u]; i; i = edges[i].nxt) {
					int v = edges[i].to;
					if (!vis[v]) vis[stk[++ns] = v] = true;
				}
			}
		} else {
			curq.res = get_cnt(curq.a);
		}

		for (int ci = 1; ci <= c && candidates[ci].d >= curq.b; ++ci) {
			if (curq.t < candidates[ci].st || candidates[ci].en <= curq.t) continue;
			int u = root(candidates[ci].u), v = root(candidates[ci].v);
			if (u == v) continue;
			mapping[u] = 0;
			mapping[v] = 0;
		}
	}
}	

int main() {
	scanf("%d %d", &n, &sm);
	for (int i = 1; i <= sm; ++i) {
		scanf("%d %d %d", &bridges[i].u, &bridges[i].v, &bridges[i].d);
	}
	scanf("%d", &sq);
	m = sm, q = 0;
	for (int t = 1; t <= sq; ++t) {
		int k, a, b;
		scanf("%d %d %d", &k, &a, &b);
		if (k == 1) {
			bridges[++m] = bridges[a];
			bridges[a].st = bridges[m].en = t;
			bridges[a].d = b;
		} else {
			queries[++q] = {t, a, b, 0};
		}
	}
	for (int i = 1; i <= sm; ++i) bridges[i].en = sq + 1;

	sort(bridges + 1, bridges + m + 1, [&](const bridge_t &lhs, const bridge_t &rhs) {
		return lhs.d > rhs.d;
	});

	for (int st = 1, en = st; st <= q; st = en) {
		for (en = st; en <= q && queries[en].t - queries[st].t - en + st <= K; ++en);
		solve(st, en);
	}

	for (int t = 1; t <= q; ++t) {
		printf("%d\n", queries[t].res);
	}
	fprintf(stderr, "%.3f\n", 1.0 * clock() / CLOCKS_PER_SEC);
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:130:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |  scanf("%d %d", &n, &sm);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
bridges.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |   scanf("%d %d %d", &bridges[i].u, &bridges[i].v, &bridges[i].d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:134:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |  scanf("%d", &sq);
      |  ~~~~~^~~~~~~~~~~
bridges.cpp:138:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |   scanf("%d %d %d", &k, &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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