Submission #410667

#	Time	Username	Problem	Language	Result	Execution time	Memory
410667		dynam1c	Bridges (APIO19_bridges)	C++17	13 / 100	3097 ms	8964 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]);
	}
};

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<pair<int, int>> es(m);
	vector<int> ws(m);
	set<pair<int, int>> s;
	for (int i = 0; i < m; i++) {
		int x, y, w;
		cin >> x >> y >> w;
		x--, y--;
		s.emplace(-w, i);
		es[i] = {x, y};
		ws[i] = w;
	}
	cin >> q;
	for (int qq = 0; qq < q; qq++) {
		int t, x, y;
		cin >> t >> x >> y;
		x--;
		if (t == 1) {
			s.erase({-ws[x], x});
			ws[x] = y;
			s.insert({-ws[x], x});
		} else {
			DSU dsu(n);
			for (auto [w, i] : s)
				if (-w < y)
					break;
				else
					dsu.unite(es[i].first, es[i].second);
			cout << dsu.sz[dsu.find(x)] << 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: 13 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27