Submission #1112440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112440		Muaath_5	Bridges (APIO19_bridges)	C++17	59 / 100	3048 ms	13696 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)

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

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

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(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(int u, int v) {
	u = root(u), v = root(v);
	if (u == v)
		return false;
	// cerr<<"CHECK "<<u<<" , "<<v<<' '
	if (cnt[u] < cnt[v]) swap(u, v);
	change(cnt[u], cnt[u]+cnt[v]);
	change(par[v], u);
	// cerr << "state: " << history.size() << ",merge " << u << ' ' << 
	//change(cnt[v], 0);
	//cerr << u << ' ' << v << ' ' << par[u] << ' ' << par[v] << ' ' << cnt[u] << ' ' << cnt[v] << endl;
	return true;
}
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];

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		edges[i].idx = i;
		cin >> edges[i].u >> edges[i].v >> edges[i].w;
		edges[i].initw = edges[i].w;
	}
	cin >> q;
	for (int i = 0; i < q; i++) {
		qrs[i].idx = i;
		cin >> qrs[i].type >> qrs[i].x >> qrs[i].y;
	}
	
	for (int ttt = 0; ttt < q; ttt++) {
		if (ttt%SQ == 0) {
			// reset dsu
			init();
			
			vector<bool> isextra(m+1, false);
			vector<vector<int>> upds(m+1);
			
			// prepare extra edges
			vector<Query> queries;
			for (int j = ttt; j < min(q, ttt+SQ); 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
			vector<Edge> extra;
			vector<Edge> mugraph;
			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(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)];
				// for (int i = 1; i <= n; i++)
					// cerr << cnt[i] << ' ';
				// cerr<<endl;
				// cerr << "Processed " << qqq.idx << ' ' << root(qqq.x) << endl;
				
				rollback(state);
			}
			
			// update the edges with their last value:
			for (int j = ttt; j < min(q, ttt+SQ); j++)
				if (qrs[j].type == 1)
					edges[qrs[j].x].initw = edges[qrs[j].x].w = qrs[j].y;
		}
		
		if (qrs[ttt].type == 2)
			cout << qrs[ttt].ans << '\n';
	}
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:47: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]
   47 |  while (history.size() > state) {
      |         ~~~~~~~~~~~~~~~^~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:110:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     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: 0 / 14
• Subtask 5: 13 / 13
• Subtask 6: 0 / 27