Submission #839245

#	Time	Username	Problem	Language	Result	Execution time	Memory
839245		mat_jur	Bridges (APIO19_bridges)	C++17	0 / 100	3064 ms	20736 KiB

bridges

#include <bits/stdc++.h>
#include <cassert>
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 debug(X) ;
#endif
#define ll long long
#define all(v) (v).begin(), (v).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define ROF(i,r,l) for(int i=(r);i>=(l);--i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
#define fi first
#define se second
#define eb emplace_back

class UF {
public:
	vector<int> e;
	int N;
	UF(int n) {N = n; e.resize(N, -1);}
	int get(int x) {return e[x] < 0 ? x : e[x] = get(e[x]);}
	int size(int x) {return -e[get(x)];}
	bool unionn(int x, int y) {
		x = get(x); y = get(y);
		if (x == y) return false;
		if (-e[x] > -e[y]) swap(x, y);
		e[y] += e[x];
		e[x] = y;
		return true;
	}	
};

int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n >> m;
	vector<tuple<int, int, int>> KR(m);
	vector<int> akt(m);
	for (auto &[d, u, v] : KR) {
		cin >> u >> v >> d;
		u--; v--;
	}
	REP(i, m) akt[i] = get<0>(KR[i]);
	int q;
	cin >> q;
	vector<tuple<int, int, int>> querys, updates;
	vector<int> ans(q);
	int cntU = 0, cntQ = 0;
	const int K = int(sqrt(q)), inf = 1e9;
	auto comp = [&](auto a, auto b) {
		return get<0>(a) > get<0>(b);
	};
	auto process = [&]() {
		vector<tuple<int, int, int, int>> kr;
		int x = 0;
		for (auto &[d, u, v] : KR) kr.eb(make_tuple(d, u, v, x++));
		sort(all(kr), comp);
		cerr << "[kr]: ";
		REP(i, m) cerr << '(' << get<1>(kr[i]) << ", " << get<2>(kr[i]) << ", " << get<0>(kr[i]) << ", " << get<3>(kr[i]) << ") ";
		vector<int> p(m), rev(m);
		x = 0;
		for (auto &[d, u, v, idx] : kr) {rev[x] = idx; p[idx] = x++;}
		for (auto &[i, b, r] : updates) b = p[b];
		sort(all(querys));
		int j = 0;
		UF sp(n);
		vector G(n, vector(0, 0));
		for(auto &[w, s, idx] : querys) {
			while (j < m && get<0>(kr[j]) >= w) {
				sp.unionn(get<1>(kr[j]), get<2>(kr[j]));
				cerr << "EDGE: " << get<1>(kr[j]) << ' ' << get<2>(kr[j]) << ' ' << get<0>(kr[j]) << ' ' << get<3>(kr[j]) << '\n';
				j++;
			}
			cerr << "QUERY: " << idx << '\n';
			debug(sp.e);
			vector<int> curr(m, inf);
			for(auto &[i, b, r] : updates) {
				if (curr[b] == inf) curr[b] = akt[rev[b]];
				if (i <= idx) curr[b] = r;
			}
			for(auto &[i, b, r] : updates) {
				if (curr[b] > max(get<0>(kr[b]), w)) {
					int u = sp.get(get<1>(kr[b])), v = sp.get(get<2>(kr[b]));
					if (u != b) {cout << "UNION: " << u << ' ' << v << '\n'; G[u].eb(v); G[v].eb(u);}
				}
			}
			vector<bool> vis(n);
			function<void(int)> dfs = [&](int v) {
				vis[v] = true;
				ans[idx] += sp.size(v);
				for (auto w : G[v]) {
					if (!vis[w]) dfs(w);
				}
			};
			dfs(sp.get(s));
			for(auto &[i, b, r] : updates) {
				if (curr[b] > max(get<0>(kr[b]), w)) {
					int u = sp.get(get<1>(kr[b])), v = sp.get(get<2>(kr[b]));
					if (u != b) {G[u].clear(); G[v].clear();}
				}
			}
		}
		cntQ = 0; cntU = 0;
		for (auto &[i, b, r] : updates) akt[b] = get<0>(KR[b]) = r;
		updates.clear();
		querys.clear();
	};
	REP(i, q) {
		int t;
		cin >> t;
		if (t == 1) {
			int b, r;
			cin >> b >> r;
			b--;
			updates.eb(make_tuple(i, b, r));
			get<0>(KR[b]) = min(get<0>(KR[b]), r);
			cntU++;
		}
		else {
			int s, w;
			cin >> s >> w;
			s--;
			querys.eb(make_tuple(w, s, i));
			cntQ++;
		}
		if (cntQ >= K || cntU >= K || i == q-1) {cerr << "PROCESS: " << i << "\n"; process();}
	}
	REP(i, q) if(ans[i] > 0) cout << ans[i] << '\n';

	return 0;
}

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