제출 #410680

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
410680		dynam1c	다리 (APIO19_bridges)	C++17	14 / 100	150 ms	8028 KiB

bridges

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define endl "\n"
#define all(c) (c).begin(),(c).end()

// when you ponder, divide and conquer

struct DSU {
	int n;
	vector<int> link, sz;
	DSU(int n) : n(n), link(n), sz(n, 1) {
		iota(all(link), 0);
	}
	void reset() {
		iota(all(link), 0);
		sz.assign(n, 1);
	}
	void unite(int u, int v) {
		u = find(u), v = find(v);
		if (u == v) return;
		if (sz[u] < sz[v]) swap(u, v);
		sz[u] += sz[v];
		link[v] = u;
	}
	int find(int v) {
		return link[v] == v ? v : link[v] = find(link[v]);
	}
};

constexpr int B = 200;
signed main() {
	// freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m, q;
	cin >> n >> m;
	vector<int> ws(m);
	vector<array<int, 3>> es(m);
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y >> ws[i];
		x--, y--;
		es[i] = {ws[i], x, y};
	}
	sort(all(ws));
	sort(all(es));
	reverse(all(es));

	cin >> q;
	vector<array<int, 3>> qs(q); // {how many edges, v, qi}
	vector<int> res(q);
	for (int qq = 0; qq < q; qq++) {
		int t, x, y;
		cin >> t >> x >> y;
		x--;
		int i = ws.end() - lower_bound(all(ws), y);
		qs[qq] = {i, x, qq};
	}
	sort(all(qs));
	DSU dsu(n);
	int ptr = 0;
	for (auto [k, v, qi] : qs) {
		while (ptr < k) {
			dsu.unite(es[ptr][1], es[ptr][2]);
			ptr++;
		}
		res[qi] = dsu.sz[dsu.find(v)];
	}
	for (int i = 0; i < q; i++)
		cout << res[i] << endl;
}
/* --- PSolving ---
 * Simplifying (getting rid of variables, conditions, code logic, etc.)
 * Reframing
 * Solving a subtask (subgoal, aux. problem, removing a condition or fixing a parameter, etc.)
 * Inducing
 * Divide and conquer
 * Working backwards
 * Visual intuition
 * !! Reductions don't have to be specializations, they can be generalizations
 */

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