제출 #938099

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
938099		mat_jur	다리 (APIO19_bridges)	C++17	73 / 100	3101 ms	8656 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
#define ll long long
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

namespace 
{
	char buf[400'000'000];
	char *buf_ptr = buf;
}

template<typename T> struct my_allocator {
	using value_type = T;
	using size_type = size_t;

	T *allocate (size_type count) {
		if(count * sizeof(T) <= 4096) {
			T *result = (T *) buf_ptr;
			buf_ptr += count * sizeof(T);
			return result;
		} else {
			return new T[count];
		}
	}

	void deallocate(T *pointer, size_type count) {
		//delete[] pointer;
	}
};

struct dynamicUF {
	vector<int> e;
	dynamicUF(int n): e(n, -1) {}
	stack<array<int, 3>> s;

	int get(int a) {return e[a] < 0 ? a : get(e[a]);}

	int unionn(int a, int b) {
		a = get(a); b = get(b);
		if(a == b) return 0;
		if(-e[a] > -e[b]) swap(a, b);
		s.push({a, b, e[a]});
		e[b] += e[a];
		e[a] = b;
		return 1;
	}

	void roll_back(int m = 1) {
		while (m--) {
			auto [a, b, sz] = s.top();
			s.pop();
			e[b] -= sz;
			e[a] = sz;
		}
	}
};

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	vector<int, my_allocator<int>> w[2], u(m), v(m);
	w[0].resize(m);
	for(int i = 0; i < m; ++i) {
		cin >> u[i] >> v[i] >> w[0][i];
		u[i]--; v[i]--;
	}

	int q;
	cin >> q;

	vector<int, my_allocator<int>> ans(q, -1);
	const int B = 600;
	vector<pair<int, int>> ev;
	vector<bool> changed(m);
	vector<int, my_allocator<int>> s(q);
	vector<int, my_allocator<int>> C(q);

	auto clean = [&](int L, int R) {
		for(int i = L; i <= R; i++) 
			if(C[i] == 1) changed[s[i]] = true;
			else ev.eb(mp(i, 1));

		dynamicUF sp(n);
		for(int i = 0; i < m; ++i) {
			if(!changed[i]) ev.eb(mp(i, 0));
			else changed[i] = false;
		}
		sort(all(ev), [&](pair<int, int> x, pair<int, int> y) {
			if (w[x.se][x.fi] != w[y.se][y.fi]) return w[x.se][x.fi] > w[y.se][y.fi];
			return x.se < y.se;
		});

		for(auto [idx, c] : ev) {
			if(c == 0) {
				sp.unionn(u[idx], v[idx]);
			}	
			else {
				int d = w[1][idx], a = s[idx], b = idx;
				map<int, int> M;
				for(int t = L; t <= R; ++t) {
					if(C[t] != 1) continue;
					if(t <= b) M[s[t]] = w[1][t];
					else if(M[s[t]] == 0) M[s[t]] = w[0][s[t]];
				}
				
				int cnt = 0;
				for(auto [idx2, r] : M) {
					if(r >= d) cnt += sp.unionn(u[idx2], v[idx2]);
				}

				ans[b] = -sp.e[sp.get(a)];
				sp.roll_back(cnt);
			}
		}

		for(int i = L; i <= R; i++) {
			if(C[i] == 1) w[0][s[i]] = w[1][i];
		}
		ev.clear();
	};

	w[1].resize(q);
	for(int t = 0; t < q; ++t) {
		cin >> C[t];
		cin >> s[t] >> w[1][t];
		s[t]--;
	}
	for(int i = 0; i < q; i += B) {
		clean(i, min(q-1, i+B-1));
	}

	for(int i = 0; i < q; i++) if(ans[i] > -1) 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: 0 / 27