Submission #1265854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265854		canhnam357	Bridges (APIO19_bridges)	C++20	100 / 100	1943 ms	12220 KiB

bridges

// source problem : 
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define MASK(i) (1LL << (i))
void ckmax(int& f, int s)
{
	f = (f > s ? f : s);
}
void ckmin(int& f, int s)
{
	f = (f < s ? f : s);
}
const int B = 800;
const int N = 1e5 + 5;
int par[N], rk[N], sz[N], pt, change[N], ord_e[N], ord_q[N];
vector<int> s[N];
void init(int n)
{
	pt = 0;
   for (int i = 0; i < n; i++)
   {
   		par[i] = i;
   		rk[i] = 0;
   		sz[i] = 1;
   }
}
int get(int x) {
    if (x == par[x]) return x;
    return get(par[x]);
}

bool join(int u, int v) {
    u = get(u);
    v = get(v);
    if (u == v) return false;

    if (rk[u] < rk[v]) swap(u, v);
    par[v] = u;

    if (rk[u] == rk[v]) {
        rk[u]++;
        s[pt++] = { u,v,1, sz[v] };
    }
    else s[pt++] = { u,v,0, sz[v] };
    sz[u] += sz[v];
    return true;
}

void rollback(int cnt) {
    while (cnt--) {
        pt--;
        par[s[pt][1]] = s[pt][1];
        if (s[pt][2] == 1) rk[s[pt][0]]--;
        sz[s[pt][0]] -= s[pt][3];
        sz[s[pt][1]] = s[pt][3];
    }
}
vector<tuple<int, int, int>> q[N / B + 1];
vector<pair<int, int>> c[N];
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<tuple<int, int, int>> e;
	for (int i = 0; i < m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		e.emplace_back(--u, --v, w);
	}
	int nq;
	cin >> nq;
	for (int i = 0; i < nq; i++)
	{
		int t, l, r;
		cin >> t >> l >> r;
		q[i / B].emplace_back(t, --l, r);
	}
	vector<int> cc;
	for (int b = 0; b <= N / B; b++)
	{
		if (q[b].empty()) break;
		init(n);
		for (int i = 0; i < m; i++) change[i] = 0;
		for (auto [t, l, r] : q[b])
		{
			if (t == 1) change[l] = 1, c[l].clear();
		}
		cc.clear();
		for (int i = 0; i < m; i++)
		{
			if (change[i]) c[i].emplace_back(-1, get<2>(e[i])), cc.push_back(i);
		}
		for (int i = 0; i < q[b].size(); i++)
		{
			auto [t, l, r] = q[b][i];
			if (t == 1)
			{
				get<2>(e[l]) = r;
				c[l].emplace_back(i, r);
			}
		}
		iota(ord_e, ord_e + m, 0);
		sort(ord_e, ord_e + m, [&](int i, int j){return get<2>(e[i]) > get<2>(e[j]);});
		iota(ord_q, ord_q + q[b].size(), 0);
		vector<int> ans(q[b].size());
		sort(ord_q, ord_q + q[b].size(), [&](int i, int j){return get<2>(q[b][i]) > get<2>(q[b][j]);});
		int j = 0;
		for (int _ = 0; _ < q[b].size(); _++)
		{
			auto [t, l, r] = q[b][ord_q[_]];
			if (t == 1) continue;
			while (j < m && get<2>(e[ord_e[j]]) >= r)
			{
				if (!change[ord_e[j]]) 
				{
					join(get<0>(e[ord_e[j]]), get<1>(e[ord_e[j]]));
				}
				j++;
			}
			int cnt = 0;
			for (int u : cc)
			{
				auto it = lower_bound(all(c[u]), make_pair(ord_q[_], 0));
				it--;
				if (it->second >= r) 
				{
					auto [z, v, w] = e[u];
					cnt += join(z, v);
				}
			}
			ans[ord_q[_]] = sz[get(l)];
			rollback(cnt);
		}
		for (int i = 0; i < q[b].size(); i++)
		{
			if (get<0>(q[b][i]) == 2) cout << ans[i] << '\n';
		}
	}
	return 0;
}

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