Submission #578068

#	Time	Username	Problem	Language	Result	Execution time	Memory
578068		JustNik77	Bridges (APIO19_bridges)	C++17	0 / 100	2563 ms	17828 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 = 500;

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 op[N], x[N], y[N];

void solve() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) cin >> v[i] >> u[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);
		for (int i = l; i < r; i++) if (op[i] == 1) used[x[i]] = 1;
		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));
		for (int i = l; i < r; i++) {
			if (op[i] == 1) {
				w[x[i]] = y[i];
			} else {
				while (!edges.empty() && get<0>(edges.back()) >= y[i])
					merge(get<1>(edges.back()), get<2>(edges.back())), edges.pop_back();
				st.clear();
				for (int id : ids) if (w[id] >= y[i]) merge(v[id], u[id]);
				cout << sz[get(x[i])] << '\n';
				rollback();
			}
		}
	}
}

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

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

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