Submission #369754

#	Time	Username	Problem	Language	Result	Execution time	Memory
369754		pavement	Bridges (APIO19_bridges)	C++17	59 / 100	3032 ms	7440 KiB

bridges

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int k = 400;
int N, M, Q, t, a, b, r, s, w, rb, uidx, idx, idx2, sa, sb, lb, link[100005], sz[100005], U[100005], V[100005], W[100005], lt[100005], out[100005];
iii T[100005];
bool used[100005];
vector<int> cons, cons2;
vector<ii> unused;
vector<iii> qbuf, ubuf;
stack<tuple<int, int, int, int, int> > rbst; 

int find(int x) {
	if (x == link[x]) return x;
	return find(link[x]);
}

void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (sz[b] > sz[a]) swap(a, b);
	rbst.emplace(a, b, sz[a], sz[b], link[b]);
	sz[a] += sz[b];
	link[b] = a;
}

void rollback() {
	assert(!rbst.empty());
	tie(a, b, sa, sb, lb) = rbst.top();
	rbst.pop();
	sz[a] = sa;
	sz[b] = sb;
	link[b] = lb;
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		link[i] = i;
		sz[i] = 1;
	}
	for (int i = 1; i <= M; i++) {
		cin >> U[i] >> V[i] >> W[i];
		T[i] = mt(W[i], U[i], V[i]);
	}
	sort(T + 1, T + 1 + M);
	cin >> Q;
	for (int i = 1; i <= Q; i++) {
		cin >> t;
		if (t == 1) {
			cin >> b >> r;
			ubuf.eb(b, r, i);
		} else {
			cin >> s >> w;
			qbuf.eb(w, s, i);
		}
		if (qbuf.size() + ubuf.size() == k) {
			uidx = 0;
			for (int i = 1; i <= N; i++) {
				link[i] = i;
				sz[i] = 1;
			}
			while (!rbst.empty()) rbst.pop();
			for (int j = 1; j <= M; j++) used[j] = lt[j] = 0;
			for (auto j : ubuf) used[g0(j)] = 1;
			unused.clear();
			for (int j = 1; j <= M; j++)
				if (!used[j]) unused.eb(W[j], j);
			sort(unused.begin(), unused.end(), greater<ii>());
			sort(qbuf.begin(), qbuf.end(), greater<iii>());
			for (auto j : qbuf) {
				tie(w, s, idx) = j;
				while (uidx < unused.size() && unused[uidx].first >= w) {
					if (find(U[unused[uidx].second]) != find(V[unused[uidx].second])) unite(U[unused[uidx].second], V[unused[uidx].second]);
					uidx++;
				}
				cons.clear();
				cons2.clear();
				bool tmp = 0;
				for (auto k : ubuf) {
					tie(b, r, idx2) = k;
					if (idx > idx2) {
						lt[b] = r;
						cons.pb(b);
					} else {
						if (!tmp) sort(cons.begin(), cons.end());
						tmp = 1;
						if (binary_search(cons.begin(), cons.end(), b)) continue;
						cons2.pb(b);
					}
				}
				rb = 0;
				for (auto k : cons) {
					if (lt[k] >= w && find(U[k]) != find(V[k])) {
						unite(U[k], V[k]);
						rb++;
					}
				}
				for (auto k : cons2) {
					if (W[k] >= w && find(U[k]) != find(V[k])) {
						unite(U[k], V[k]);
						rb++;
					}
				}
				out[idx] = sz[find(s)];
				while (rb--) rollback();
			}
			for (auto j : ubuf) W[g0(j)] = g1(j);
			qbuf.clear();
			ubuf.clear();
		}
	}
	uidx = 0;
	for (int i = 1; i <= N; i++) {
		link[i] = i;
		sz[i] = 1;
	}
	while (!rbst.empty()) rbst.pop();
	for (int j = 1; j <= M; j++) used[j] = lt[j] = 0;
	for (auto j : ubuf) used[g0(j)] = 1;
	unused.clear();
	for (int j = 1; j <= M; j++)
		if (!used[j]) unused.eb(W[j], j);
	sort(unused.begin(), unused.end(), greater<ii>());
	sort(qbuf.begin(), qbuf.end(), greater<iii>());
	for (auto j : qbuf) {
		tie(w, s, idx) = j;
		while (uidx < unused.size() && unused[uidx].first >= w) {
			if (find(U[unused[uidx].second]) != find(V[unused[uidx].second])) unite(U[unused[uidx].second], V[unused[uidx].second]);
			uidx++;
		}
		cons.clear();
		cons2.clear();
		bool tmp = 0;
		for (auto k : ubuf) {
			tie(b, r, idx2) = k;
			if (idx > idx2) {
				lt[b] = r;
				cons.pb(b);
			} else {
				if (!tmp) sort(cons.begin(), cons.end());
				tmp = 1;
				if (binary_search(cons.begin(), cons.end(), b)) continue;
				cons2.pb(b);
			}
		}
		rb = 0;
		for (auto k : cons) {
			if (lt[k] >= w && find(U[k]) != find(V[k])) {
				unite(U[k], V[k]);
				rb++;
			}
		}
		for (auto k : cons2) {
			if (W[k] >= w && find(U[k]) != find(V[k])) {
				unite(U[k], V[k]);
				rb++;
			}
		}
		out[idx] = sz[find(s)];
		while (rb--) rollback();
	}
	for (auto j : ubuf) W[g0(j)] = g1(j);
	for (int i = 1; i <= Q; i++)
		if (out[i]) cout << out[i] << '\n';
}

Compilation message (stderr)

bridges.cpp:59:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   59 | main() {
      |      ^
bridges.cpp: In function 'int main()':
bridges.cpp:89:49: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   89 |    for (int j = 1; j <= M; j++) used[j] = lt[j] = 0;
      |                                           ~~~~~~^~~
bridges.cpp:98:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     while (uidx < unused.size() && unused[uidx].first >= w) {
      |            ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:144:47: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  144 |  for (int j = 1; j <= M; j++) used[j] = lt[j] = 0;
      |                                         ~~~~~~^~~
bridges.cpp:153:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |   while (uidx < unused.size() && unused[uidx].first >= w) {
      |          ~~~~~^~~~~~~~~~~~~~~

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