Submission #388949

#	Time	Username	Problem	Language	Result	Execution time	Memory
388949		sinamhdv	Bridges (APIO19_bridges)	C++11	100 / 100	2914 ms	11988 KiB

bridges

// APIO19_bridges
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 50100
#define MAXE 100100
#define SQ 1000

int n, m, q;
int efrom[MAXE], eto[MAXE], ew[MAXE];
int ans[MAXE];
int tp[MAXE], qx[MAXE], qy[MAXE];
vector<int> asks[MAXE / SQ + 10];	// indexes of asks sorted by w
unordered_set<int> upds[MAXE / SQ + 10];	// edges that get updated
vector<int> edge;
int curw[MAXE];

// dsu
vector<int> undo_stk;
int dsu[MAXN];
int sz[MAXN];

int getroot(int x)
{
	return dsu[x] == x ? x : getroot(dsu[x]);
}

void merge(int x, int y)
{
	x = getroot(x);
	y = getroot(y);
	if (x == y)
	{
		undo_stk.pb(-1);
		return;
	}
	if (sz[x] > sz[y]) swap(x, y);
	dsu[x] = y;
	sz[y] += sz[x];
	undo_stk.pb(x);
}

void undo(void)
{
	int x = undo_stk.back();
	undo_stk.pop_back();
	if (x < 0) return;
	sz[dsu[x]] -= sz[x];
	dsu[x] = x;
}

void rebuild(int b)
{
	// clear dsu
	undo_stk.clear();
	iota(dsu, dsu + n + 10, 0);
	fill(sz, sz + n + 10, 1);

	// sort edges
	edge.clear();
	FOR(i, 0, m)
		if (upds[b].find(i) == upds[b].end())
			edge.pb(i);
	sort(all(edge), [&](int x, int y){ return ew[x] < ew[y]; });

	// sort asks
	sort(all(asks[b]), [&](int x, int y){ return qy[x] > qy[y]; });
}

int32_t main(void)
{
	fast_io;
	cin >> n >> m;
	FOR(i, 0, m)
	{
		cin >> efrom[i] >> eto[i] >> ew[i];
	}
	cin >> q;
	FOR(i, 0, q)
	{
		cin >> tp[i] >> qx[i] >> qy[i];
		if (tp[i] == 2) asks[i/SQ].pb(i);
		else
		{
			qx[i]--;
			upds[i / SQ].insert(qx[i]);
		}
	}

	for (int b = 0; b <= q/SQ; b++)
	{
		rebuild(b);

		int ptr = edge.size() - 1;
		for (int i : asks[b])
		{
			while (ptr >= 0 && ew[edge[ptr]] >= qy[i])
			{
				merge(efrom[edge[ptr]], eto[edge[ptr]]);
				ptr--;
			}

			// merge recent edges
			vector<int> upe;
			for (int e : upds[b]) upe.pb(e);
			for (int e : upe) curw[e] = ew[e];
			FOR(j, b * SQ, i)
			{
				if (tp[j] == 2) continue;
				curw[qx[j]] = qy[j];
			}
			int cnt = 0;
			for (int e : upe) if (curw[e] >= qy[i]) merge(efrom[e], eto[e]), cnt++;;

			// answer the query
			ans[i] = sz[getroot(qx[i])];

			// undo dsu
			FOR(j, 0, cnt)
				undo();
		}

		FOR(i, b * SQ, min(q + 1, (b +1) * SQ)) if (tp[i] == 1) ew[qx[i]] = qy[i];
	}

	FOR(i, 0, q) if (tp[i] == 2)
		cout << ans[i] << endl;

	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