Submission #1112602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112602		Muaath_5	Bridges (APIO19_bridges)	C++17	100 / 100	1985 ms	14664 KiB

bridges

// Problem: E - Bridges
// Contest: Virtual Judge - Square root tech
// URL: https://vjudge.net/contest/671583#problem/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// By Muaath Alqarni
// Blog: https://muaath5.githib.io/blog
// 
// Powered by CP Editor (https://cpeditor.org)

#pragma GCC optimize("Ofast,O3,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

const int N = 5e4+5, M = 1e5+1, SQ = 900;

int n, m, q;

int par[N], cnt[N];
vector<pair<int&, int>> history;
void init() {
	history.clear();
	for (int i = 1; i <= n; i++)
		par[i] = i, cnt[i] = 1;
}	
int root_static(int x) {return par[x]==x?x:par[x]=root_static(par[x]);}
int root(int x) {return par[x]==x?x:root(par[x]);}
void change(int &a, int b) {
	history.push_back({a, a});
	a = b;
}
bool merge_static(int u, int v) {
	u = root_static(u), v = root_static(v);
	if (u == v)
		return false;
	if (cnt[u] < cnt[v]) swap(u, v);
	cnt[u] += cnt[v];
	par[v] = u;
	return true;
}
bool merge(int u, int v) {
	u = root(u), v = root(v);
	if (u == v)
		return false;
	if (cnt[u] < cnt[v]) swap(u, v);
	change(cnt[u], cnt[u]+cnt[v]);
	change(par[v], u);
	return true;
}
inline void rollback(int state) {
	while (history.size() > state) {
		history.back().first = history.back().second;
		history.pop_back();
	}
}

struct Edge {
	int idx, u, v, w, initw;
} edges[M];
struct Query {
	int idx, type, x, y, ans;
} qrs[M];

static inline int read()
{
    int x = 0;char ch = getchar();
    while (ch < '0' || ch>'9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x;
}

static inline void print(const int &x) {
    if (x > 9)print(x / 10);
    putchar('0' + x % 10);
}

bool isextra[M];

int main()
{
	n=read(), m=read();
	for (int i = 1; i <= m; i++) {
		edges[i].idx = i;
		edges[i].u=read(), edges[i].v=read(), edges[i].w=read();
		edges[i].initw = edges[i].w;
	}
	q=read();
	for (int i = 0; i < q; i++) {
		qrs[i].idx = i;
		qrs[i].type=read(), qrs[i].x=read(), qrs[i].y=read();
	}
	
	history.reserve(m);
	vector<vector<int>> upds(m+1);
	vector<Edge> extra, mugraph;
	extra.reserve(SQ);
	mugraph.reserve(m);
	int blksz = 0;
	int updcnt = 0;
	for (int tt = 0; tt < q; tt++) {
		blksz++;
		if (qrs[tt].type == 1) updcnt++;
		if (updcnt == SQ || tt == q-1) {
			int ttt = tt-blksz+1;
			
			// reset dsu
			init();
			
			// prepare extra edges
			vector<Query> queries;
			queries.reserve(blksz-updcnt);
			for (int j = ttt; j < min(q, ttt+blksz); j++)
				if (qrs[j].type == 2)
					queries.push_back(qrs[j]);
				else {
					upds[qrs[j].x].push_back(j);
					isextra[qrs[j].x] = true;
				}
					
			// put edges in sorted order
			mugraph.clear();
			extra.clear();
			for (int i = 1; i <= m; i++) {
				if (!isextra[i])
					mugraph.push_back(edges[i]);
				else
					extra.push_back(edges[i]);
			}
			
			sort(mugraph.begin(), mugraph.end(),
				[](Edge x, Edge y){ return x.w > y.w; });
			sort(queries.begin(), queries.end(),
				[](Query x, Query y){ return x.y > y.y; });
			
			int mu_idx = 0;
			for (auto qqq : queries) {
				while (mu_idx < mugraph.size() && mugraph[mu_idx].w >= qqq.y) {
					merge_static(mugraph[mu_idx].u, mugraph[mu_idx].v);
					mu_idx++;
				}
	
				int state = history.size();
				for (auto ee : extra) {
					if (upds[ee.idx][0] < qqq.idx) {
						ee.w = qrs[*prev(upper_bound(upds[ee.idx].begin(), upds[ee.idx].end(), qqq.idx))].y;
					}
					else
						ee.w = ee.initw;
					if (ee.w >= qqq.y)
						merge(ee.u, ee.v);
				}
				
				qrs[qqq.idx].ans = cnt[root(qqq.x)];
				rollback(state);
			}
			
			// update the edges with their last value:
			for (int j = ttt; j < min(q, ttt+blksz); j++)
				if (qrs[j].type == 1) {
					upds[qrs[j].x].clear();
					isextra[qrs[j].x] = false;
					edges[qrs[j].x].initw = edges[qrs[j].x].w = qrs[j].y;
				}
			blksz = updcnt = 0;
		}
	}
	
	for (int i = 0; i < q; i++)
		if (qrs[i].type == 2) {
			print(qrs[i].ans);
			putchar('\n');
		}
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:54:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int&, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |  while (history.size() > state) {
      |         ~~~~~~~~~~~~~~~^~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:140:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     while (mu_idx < mugraph.size() && mugraph[mu_idx].w >= qqq.y) {
      |            ~~~~~~~^~~~~~~~~~~~~~~~

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