Submission #1045935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045935		Onur_Ilgaz	Bridges (APIO19_bridges)	C++17	100 / 100	2217 ms	9292 KiB

bridges

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define inf ((int)1e9)
using namespace std;
const int SQ = 600;

struct DSU {
	int n;
	vector <int> par, w;
	stack <pair<int, int> > st;
	DSU(int size) {
		n = size;
		par.resize(n + 1);
		w.resize(n + 1, 1);
		for(int i = 1; i <= n; i++) par[i] = i;
	}
	int parent(int x) {
		if(par[x] == x) return x;
		return parent(par[x]);
	}
	void merge(int a, int b) {
		a = parent(a);
		b = parent(b);
		if(w[a] < w[b]) swap(a, b);
		if(a == b) {
			st.push({-1, -1});
			return;
		}
		// byi aya ekle
		st.push({b, a});
		par[b] = a;
		w[a] += w[b];
	} 
	void pop() {
		auto [b, a] = st.top();
		st.pop();
		if(b == -1) return;
		par[b] = b;
		w[a] -= w[b];
	}
	int getw(int node) {
		return w[parent(node)];
	}
};

int32_t main(){
	fast
	int n, m;
	cin >> n >> m;
	vector <array<int, 3> > edges, u, qs;
	vector <array<int, 4> > qq;
	for(int i = 0; i < m; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		edges.push_back({w, a, b});
	}
	int q;
	cin >> q;
	vector <int> ans(q);
	for(int i = 0; i < q; i++) {
		int type, a, b;
		cin >> type >> a >> b;
		if(type == 2) qq.push_back({type, b, a, i}); // type, val, stnode, ind
		else qq.push_back({type, a - 1, -i, b});
	}
	for(int seg = 0; seg * SQ < q; seg++) {
		int st = seg * SQ, nd = min(q, st + SQ);
		{
			sort(qq.begin() + st, qq.begin() + nd);
			reverse(qq.begin() + st, qq.begin() + nd);
		}
		vector <bool> changed(m);
		vector <array<int, 3> > unchanged, tmp = edges;
		for(int j = st; j < nd; j++) {
			if(qq[j][0] == 1) {
				auto [_, edge, ind, w] = qq[j];
				u.push_back({edge, w, -ind}); // edge, w, ind
				changed[edge] = 1;
				tmp[edge][0] = w;
			}
			else {
				qs.push_back({qq[j][2], qq[j][1], qq[j][3]}); // stnode, val, ind
			}
		}
		for(int i = 0; i < m; i++) {
			if(!changed[i]) {
				unchanged.push_back(edges[i]);
			}
		}
		sort(unchanged.begin(), unchanged.end());
		reverse(unchanged.begin(), unchanged.end());
		int l = 0;
		DSU dsu(n);
		for(auto [stnode, val, ind]:qs) {
			while(l < unchanged.size() and unchanged[l][0] >= val) {
				// cout << "premerge " << unchanged[l][1] << " " << unchanged[l][2] << "\n";
				dsu.merge(unchanged[l][1], unchanged[l][2]);
				l++;
			}
			int cnt = 0;
			for(int i = 0; i < u.size(); i++) { // edge, w, ind
				if(u[i][1] >= val and u[i][2] < ind and (i + 1 == u.size() or u[i][0] != u[i + 1][0] or u[i + 1][2] > ind)) {
					dsu.merge(edges[u[i][0]][1], edges[u[i][0]][2]);
					cnt++;
				}
				else if(u[i][2] > ind and (!i or u[i - 1][0] != u[i][0]) and edges[u[i][0]][0] >= val) { // add for default
					dsu.merge(edges[u[i][0]][1], edges[u[i][0]][2]);
					cnt++;
				}
			}
			ans[ind] = dsu.getw(stnode);
			while(cnt--) {
				dsu.pop();
			}
		}
		edges = tmp;
		qs.clear();
		u.clear();
	}
	for(auto it:ans) {
		if(it) cout << it << "\n";
	}
}

Compilation message (stderr)

bridges.cpp: In function 'int32_t main()':
bridges.cpp:95:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |    while(l < unchanged.size() and unchanged[l][0] >= val) {
      |          ~~^~~~~~~~~~~~~~~~~~
bridges.cpp:101:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |    for(int i = 0; i < u.size(); i++) { // edge, w, ind
      |                   ~~^~~~~~~~~~
bridges.cpp:102:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     if(u[i][1] >= val and u[i][2] < ind and (i + 1 == u.size() or u[i][0] != u[i + 1][0] or u[i + 1][2] > ind)) {
      |                                              ~~~~~~^~~~~~~~~~~

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