Submission #369807

#	Time	Username	Problem	Language	Result	Execution time	Memory
369807		pavement	Bridges (APIO19_bridges)	C++17	100 / 100	2991 ms	8652 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 = 600;
int N, M, Q, unusedidx, qbufidx, ubufidx, considx, cons2idx, 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], cons[100005], cons2[100005];
bitset<100005> used;
ii unused[100005];
iii qbuf[100005], ubuf[100005];
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;
}
 
inline void read(int &v) {
    v = 0;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    for (; ch >= '0' && ch <= '9'; ch = getchar_unlocked())
        v = (v << 1) + (v << 3) + (ch & 15);
}
 
void proc() {
	uidx = unusedidx = 0;
	for (int i = 1; i <= N; i++) {
		link[i] = i;
		sz[i] = 1;
	}
	while (!rbst.empty()) rbst.pop();
	used.reset();
	for (int j = 0; j < ubufidx; j++) used[g0(ubuf[j])] = 1;
	for (int j = 1; j <= M; j++)
		if (!used[j]) unused[unusedidx++] = mp(W[j], j);
	sort(unused, unused + unusedidx, greater<ii>());
	sort(qbuf, qbuf + qbufidx, greater<iii>());
	for (int j = 0; j < qbufidx; j++) {
		tie(w, s, idx) = qbuf[j];
		while (uidx < unusedidx && 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++;
		}
		considx = cons2idx = 0;
		for (int k = 0; k < ubufidx; k++) {
			tie(b, r, idx2) = ubuf[k];
			if (idx > idx2) {
				lt[b] = r;
				cons[considx++] = b;
			} else {
				if (lt[b]) continue;
				cons2[cons2idx++] = b;
			}
		}
		rb = 0;
		for (int k = 0; k < considx; k++) {
			if (lt[cons[k]] >= w && find(U[cons[k]]) != find(V[cons[k]])) {
				unite(U[cons[k]], V[cons[k]]);
				rb++;
			}
		}
		for (int k = 0; k < considx; k++)
			lt[cons[k]] = 0;
		for (int k = 0; k < cons2idx; k++) {
			if (W[cons2[k]] >= w && find(U[cons2[k]]) != find(V[cons2[k]])) {
				unite(U[cons2[k]], V[cons2[k]]);
				rb++;
			}
		}
		out[idx] = sz[find(s)];
		while (rb--) rollback();
	}
	for (int j = 0; j < ubufidx; j++) W[g0(ubuf[j])] = g1(ubuf[j]);
	qbufidx = ubufidx = 0;
}

main() {
	read(N);
	read(M);
	for (int i = 1; i <= N; i++) {
		link[i] = i;
		sz[i] = 1;
	}
	for (int i = 1; i <= M; i++) {
		read(U[i]);
		read(V[i]);
		read(W[i]);
	}
	read(Q);
	for (int i = 1; i <= Q; i++) {
		read(t);
		if (t == 1) {
			read(b);
			read(r);
			ubuf[ubufidx++] = mt(b, r, i);
		} else {
			read(s);
			read(w);
			qbuf[qbufidx++] = mt(w, s, i);
		}
		if (qbufidx + ubufidx == k) proc();
	}
	proc();
	for (int i = 1; i <= Q; i++)
		if (out[i]) printf("%d\n", out[i]);
}

Compilation message (stderr)

bridges.cpp:117:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  117 | main() {
      |      ^

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