Submission #578070

#	Time	Username	Problem	Language	Result	Execution time	Memory
578070		JustNik77	Bridges (APIO19_bridges)	C++17	100 / 100	2358 ms	11584 KiB

bridges

#define _USE_MATH_DEFINES

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("unswitch-loops")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("rename-registers")

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
#include <stack>
#include <bitset>
#include <map>
#include <ctime>
#include <numeric>
#include <random>
#include <cassert>
#include <cstring>
#include <chrono>

//#define int long long
#define uint unsigned long long
#define double long double
#define INF (int) 1e18 / 2
#define all(a) a.begin(), a.end()
#define debug(a) cerr << #a << ": " << a << endl
#define YES return (void) (cout << "Yes\n")
#define NO return (void) (cout << "No\n")
#define ls x << 1
#define rs x << 1 | 1

#ifdef JUSTNIK
#define start cout.setf(ios::fixed); cout.precision(10); int START = clock()
#define finish cout << "\ntime: " << (clock() - START) / (double)(CLOCKS_PER_SEC); return 0
#else
#define start cin.tie(NULL); cout.tie(NULL); cout.setf(ios::fixed); cout.precision(10); ios_base::sync_with_stdio(false)
#define finish return 0
#endif

using namespace std;


mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e5 + 5, sq = 750;

int n, m, q;
int p[N], sz[N];

int get(int i) { return i == p[i] ? i : get(p[i]); }

vector<int> st;

void merge(int i, int j) {
	i = get(i);
	j = get(j);
	if (i == j) return;
	if (sz[i] < sz[j]) swap(i, j);
	sz[i] += sz[j];
	p[j] = i;
	st.push_back(j);
}

void rollback() {
	while (!st.empty()) {
		int j = st.back();
		int i = p[j];
		sz[i] -= sz[j];
		p[j] = j;
		st.pop_back();
	}
}

int v[N], u[N], w[N];
int last[N];
int op[N], x[N], y[N];
int res[N];

void solve() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) cin >> v[i] >> u[i] >> w[i], last[i] = w[i];
	cin >> q;
	for (int i = 0; i < q; i++) cin >> op[i] >> x[i] >> y[i];
	for (int l = 0; l < q; l += sq) {
		iota(p, p + N, 0);
		fill(sz, sz + N, 1);
		int r = min(q, l + sq);
		vector<int> used(m + 1);
		vector<tuple<int, int, int>> ask;
		for (int i = l; i < r; i++) {
			if (op[i] == 1) {
				used[x[i]] = 1;
			} else {
				ask.push_back({y[i], x[i], i});
			}
		}
		vector<int> ids;
		vector<tuple<int, int, int>> edges;
		for (int i = 1; i <= m; i++) {
			if (used[i]) ids.push_back(i);
			else edges.push_back({w[i], v[i], u[i]});
		}
		sort(all(edges));
		sort(all(ask));
		reverse(all(ask));
		for (auto[cur, s, i] : ask) {
			for (int id : ids)
				last[id] = w[id];
			while (!edges.empty() && get<0>(edges.back()) >= cur)
				merge(get<1>(edges.back()), get<2>(edges.back())), edges.pop_back();
			st.clear();
			for (int j = l; j < r; j++)
				if (op[j] == 1 && j < i) last[x[j]] = y[j];
			for (int id : ids)
				if (last[id] >= cur) merge(v[id], u[id]);
			res[i] = sz[get(s)];
			rollback();
		}
		for (int i = l; i < r; i++)
			if (op[i] == 1) w[x[i]] = y[i];
	}
	for (int i = 0; i < q; i++) if (op[i] == 2) cout << res[i] << '\n';
}

int32_t main() {
	start;
	
	solve();
	
	finish;
}

/*
     ▄▀▀▀▄
▄███▀░◐░░░▌
    ▌░░░░░▐
    ▐░░░░░▐
    ▌░░░░░▐▄▄
    ▌░░░░▄▀▒▒▀▀▀▀▄
   ▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
   ▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
    ▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
      ▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
           ▌▌░▌▌
           ▌▌░▌▌
         ▄▄▌▌▄▌▌        */

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