oj.uz

Submission #159336

# Submission time Handle Problem Language Result Execution time Memory
159336 2019-10-22T11:15:42 Z iefnah06 Bridges (APIO19_bridges) C++11
44 / 100
 3000 ms 14140 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 42 ms 5468 KB Output is correct
4 Correct 11 ms 5496 KB Output is correct
5 Correct 20 ms 5340 KB Output is correct
6 Correct 20 ms 5496 KB Output is correct
7 Correct 16 ms 5240 KB Output is correct
8 Correct 16 ms 5368 KB Output is correct
9 Correct 18 ms 5368 KB Output is correct
10 Correct 17 ms 5368 KB Output is correct
11 Correct 16 ms 5368 KB Output is correct
12 Correct 16 ms 5368 KB Output is correct
13 Correct 19 ms 5368 KB Output is correct
14 Correct 18 ms 5368 KB Output is correct
15 Correct 18 ms 5368 KB Output is correct
16 Correct 16 ms 5240 KB Output is correct
17 Correct 16 ms 5368 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2277 ms 13156 KB Output is correct
2 Correct 2278 ms 12840 KB Output is correct
3 Correct 2315 ms 12692 KB Output is correct
4 Correct 2213 ms 12996 KB Output is correct
5 Correct 2252 ms 12896 KB Output is correct
6 Execution timed out 3032 ms 11580 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1859 ms 11736 KB Output is correct
2 Correct 795 ms 9168 KB Output is correct
3 Correct 2059 ms 11208 KB Output is correct
4 Correct 1818 ms 11676 KB Output is correct
5 Correct 52 ms 8184 KB Output is correct
6 Correct 1882 ms 11440 KB Output is correct
7 Correct 1693 ms 11616 KB Output is correct
8 Correct 1580 ms 11692 KB Output is correct
9 Correct 1110 ms 10816 KB Output is correct
10 Correct 1043 ms 11012 KB Output is correct
11 Correct 1281 ms 11304 KB Output is correct
12 Correct 1165 ms 11360 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1898 ms 14072 KB Output is correct
2 Correct 52 ms 8184 KB Output is correct
3 Correct 2250 ms 10360 KB Output is correct
4 Correct 1022 ms 10428 KB Output is correct
5 Correct 1786 ms 12584 KB Output is correct
6 Correct 1900 ms 14064 KB Output is correct
7 Correct 1879 ms 12600 KB Output is correct
8 Correct 968 ms 11304 KB Output is correct
9 Correct 972 ms 11516 KB Output is correct
10 Correct 968 ms 11328 KB Output is correct
11 Correct 1563 ms 13012 KB Output is correct
12 Correct 1550 ms 13196 KB Output is correct
13 Correct 1524 ms 12972 KB Output is correct
14 Correct 1520 ms 12624 KB Output is correct
15 Correct 1633 ms 12604 KB Output is correct
16 Correct 1951 ms 14008 KB Output is correct
17 Correct 1977 ms 13912 KB Output is correct
18 Correct 1950 ms 14064 KB Output is correct
19 Correct 1953 ms 14140 KB Output is correct
20 Correct 1735 ms 13108 KB Output is correct
21 Correct 1715 ms 13024 KB Output is correct
22 Correct 1907 ms 13812 KB Output is correct
23 Correct 1804 ms 12036 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2277 ms 13156 KB Output is correct
2 Correct 2278 ms 12840 KB Output is correct
3 Correct 2315 ms 12692 KB Output is correct
4 Correct 2213 ms 12996 KB Output is correct
5 Correct 2252 ms 12896 KB Output is correct
6 Execution timed out 3032 ms 11580 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 42 ms 5468 KB Output is correct
4 Correct 11 ms 5496 KB Output is correct
5 Correct 20 ms 5340 KB Output is correct
6 Correct 20 ms 5496 KB Output is correct
7 Correct 16 ms 5240 KB Output is correct
8 Correct 16 ms 5368 KB Output is correct
9 Correct 18 ms 5368 KB Output is correct
10 Correct 17 ms 5368 KB Output is correct
11 Correct 16 ms 5368 KB Output is correct
12 Correct 16 ms 5368 KB Output is correct
13 Correct 19 ms 5368 KB Output is correct
14 Correct 18 ms 5368 KB Output is correct
15 Correct 18 ms 5368 KB Output is correct
16 Correct 16 ms 5240 KB Output is correct
17 Correct 16 ms 5368 KB Output is correct
18 Correct 2277 ms 13156 KB Output is correct
19 Correct 2278 ms 12840 KB Output is correct
20 Correct 2315 ms 12692 KB Output is correct
21 Correct 2213 ms 12996 KB Output is correct
22 Correct 2252 ms 12896 KB Output is correct
23 Execution timed out 3032 ms 11580 KB Time limit exceeded
24 Halted 0 ms 0 KB -