Submission #159336

#	Time	Username	Problem	Language	Result	Execution time	Memory
159336		iefnah06	Bridges (APIO19_bridges)	C++11	44 / 100	3032 ms	14140 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

// 把操作分块，每次回答每块内询问的答案
// 对于块前面的修改，把询问和这些修改按照边权降序排序，把前面的修改直接用并查集合并
// 对于块内的，暴力建图计算影响

const int MAXN = 2e5;
int N, M; 
int S;
int A[MAXN], B[MAXN], C[MAXN];

int Q;
int T[MAXN], X[MAXN], Y[MAXN];
int ans[MAXN];

bool vis[MAXN];

struct dsu {
	int par[MAXN], sz[MAXN];

	int getpar(int a) {
		return par[a] == -1 ? a : (par[a] = getpar(par[a]));
	}

	void merge(int a, int b) {
		a = getpar(a), b = getpar(b);
		if (a != b) {
			if (sz[a] > sz[b]) swap(a, b);
			sz[b] += sz[a];
			par[a] = b;
		}
	}

	void reset() {
		fill(par + 1, par + N + 1, -1);
		fill(sz + 1, sz + N + 1, 1);
	}

	int size(int a) const {
		return sz[a];
	}
} conn;

vector<int> adj[MAXN];

void add(int a, int b) {
	assert(1 <= a && a <= N);
	assert(1 <= b && b <= N);
	a = conn.getpar(a), b = conn.getpar(b);
	adj[a].push_back(b);
	adj[b].push_back(a);
}

int dfs(int cur) {
	vis[cur] = true;
	int res = conn.size(cur);
	for (int nxt : adj[cur]) {
		if (!vis[nxt]) {
			res += dfs(nxt);
		}
	}
	return res;
}

int main() {
	scanf("%d %d", &N, &M);
	S = max(1, int(sqrt(N * log2(N))));
	for (int i = 0; i < M; i++) {
		scanf("%d %d %d", &A[i], &B[i], &C[i]);
	}
	scanf("%d", &Q);
	for (int i = 0; i < Q; i++) {
		scanf("%d %d %d", &T[i], &X[i], &Y[i]);
		if (T[i] == 1) X[i]--;
	}

	for (int st = 0; st < Q; st += S) {
		int ed = min(Q, st + S);

		vector<pair<int, int>> evts;
		for (int i = st; i < ed; i++) {
			if (T[i] == 1) {
				vis[X[i]] = true;
			} else {
				evts.emplace_back(Y[i], ~i); // < 0
			}
		}
		vector<int> special;
		for (int i = 0; i < M; i++) {
			if (vis[i]) {
				special.push_back(i);
			} else {
				evts.emplace_back(C[i], i); // >= 0
			}
		}
		for (int i = st; i < ed; i++) {
			if (T[i] == 1) {
				vis[X[i]] = false;
			}
		}

		sort(evts.begin(), evts.end(), greater<pair<int, int>>());
		conn.reset();
		for (const auto& ev : evts) {
			int w, i; tie(w, i) = ev;
			if (i >= 0) {
				conn.merge(A[i], B[i]);
			} else {
				i = ~i;
				for (int j = i - 1; j >= st; j--) {
					if (T[j] != 1 || vis[X[j]]) continue;
					vis[X[j]] = true;
					if (Y[j] >= w) {
						add(A[X[j]], B[X[j]]);
					}
				}
				for (const auto& j : special) {
					if (vis[j]) {
						vis[j] = false;
					} else if (C[j] >= w) {
						add(A[j], B[j]);
					}
				}

				ans[i] = dfs(conn.getpar(X[i]));

				// reset
				vis[conn.getpar(X[i])] = false;
				for (const auto& j : special) {
					int a = conn.getpar(A[j]);
					int b = conn.getpar(B[j]);
					adj[a].clear(), adj[b].clear();
					vis[a] = false, vis[b] = false;
				}
			}
		}

		for (int i = st; i < ed; i++) {
			if (T[i] == 1) {
				C[X[i]] = Y[i];
			}
		}
	}

	for (int i = 0; i < Q; i++) {
		if (T[i] == 2) {
			printf("%d\n", ans[i]);
		}
	}

	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &A[i], &B[i], &C[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
bridges.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &T[i], &X[i], &Y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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