제출 #727083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
727083		SanguineChameleon	다리 (APIO19_bridges)	C++17	100 / 100	2898 ms	19572 KiB

bridges

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

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

struct edge {
	int u, v, w;
};

struct query {
	int t, x, y, res;
};

const int maxN = 1e5 + 20;
const int block = 1000;
vector<pair<int, int>> adj[maxN];
edge E[maxN];
query Q[maxN];
bool imp_edge[maxN];
bool imp_node[maxN];
int depth[maxN];
int par[maxN];
int sz[maxN];
vector<int> comp[maxN];
vector<pair<int, int>> vals[maxN];
int flag_comp[maxN];
int flag_imp[maxN];

int root(int u) {
	if (!par[u]) {
		return u;
	}
	return (par[u] = root(par[u]));
}

void update(int u, int v) {
	int ru = root(u);
	int rv = root(v);
	if (ru == rv) {
		return;
	}
	if (depth[ru] > depth[rv]) {
		swap(ru, rv);
	}
	par[ru] = rv;
	sz[rv] += sz[ru];
	if (comp[ru].size() > comp[rv].size()) {
		swap(comp[ru], comp[rv]);
	}
	comp[rv].insert(comp[rv].end(), comp[ru].begin(), comp[ru].end());
	if (depth[ru] == depth[rv]) {
		depth[rv]++;
	}
}

void dfs(int u, int w, int query_id) {
	if (flag_imp[u] == query_id) {
		return;
	}
	flag_imp[u] = query_id;
	int ru = root(u);
	if (flag_comp[ru] != query_id) {
		Q[query_id].res += sz[ru];
		flag_comp[ru] = query_id;
		for (auto v: comp[ru]) {
			dfs(v, w, query_id);
		}
	}
	for (auto e: adj[u]) {
		int v = e.first;
		int edge_id = e.second;
		int cur = (lower_bound(vals[edge_id].begin(), vals[edge_id].end(), make_pair(query_id, -1)) - 1)->second;
		if (w <= cur) {
			dfs(v, w, query_id);
		}
	}
}

void just_do_it() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> E[i].u >> E[i].v >> E[i].w;
	}
	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		cin >> Q[i].t >> Q[i].x >> Q[i].y;
	}
	for (int i = 1; i <= n; i++) {
		flag_comp[i] = -1;
		flag_imp[i] = -1;
	}
	for (int block_id = 0; block_id <= (q - 1) / block; block_id++) {
		int lt = block_id * block;
		int rt = min((block_id + 1) * block - 1, q - 1);
		for (int i = 1; i <= n; i++) {
			adj[i].clear();
			imp_node[i] = false;
		}
		for (int i = 1; i <= m; i++) {
			imp_edge[i] = false;
		}
		vector<pair<int, int>> events;
		for (int i = lt; i <= rt; i++) {
			if (Q[i].t == 1) {
				imp_edge[Q[i].x] = true;
			}
			else {
				events.emplace_back(Q[i].y, -i);
			}
		}
		for (int i = 1; i <= m; i++) {
			if (imp_edge[i]) {
				vals[i].clear();
				vals[i].emplace_back(lt - 1, E[i].w);
				int u = E[i].u;
				int v = E[i].v;
				imp_node[u] = true;
				imp_node[v] = true;
				adj[u].emplace_back(v, i);
				adj[v].emplace_back(u, i);
			}
			else {
				events.emplace_back(E[i].w, i);
			}
		}
		for (int i = lt; i <= rt; i++) {
			if (Q[i].t == 1) {
				vals[Q[i].x].emplace_back(i, Q[i].y);
				E[Q[i].x].w = Q[i].y;
			}
		}
		for (int i = 1; i <= n; i++) {
			depth[i] = 0;
			par[i] = 0;
			sz[i] = 1;
			comp[i].clear();
			if (imp_node[i]) {
				comp[i].emplace_back(i);
			}
		}
		sort(events.begin(), events.end(), greater<pair<int, int>>());
		for (auto e: events) {
			int id = e.second;
			if (id > 0) {
				int u = E[id].u;
				int v = E[id].v;
				update(u, v);
			}
			else {
				id = -id;
				int u = Q[id].x;
				int w = Q[id].y;
				Q[id].res = 0;
				dfs(u, w, id);
			}
		}
	}
	for (int i = 0; i < q; i++) {
		if (Q[i].t == 2) {
			cout << Q[i].res << '\n';
		}
	}
}

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