Submission #1045885

#TimeUsernameProblemLanguageResultExecution timeMemory
1045885vjudge1Bridges (APIO19_bridges)C++17
100 / 100
2276 ms8692 KiB
#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;
			// cout << "for query: " << stnode << " " << val << " " << ind << ":\n";
			for(int i = 0; i < u.size(); i++) { // edge, w, ind
				// cout << "update " << u[i][0] + 1 << " " << u[i][1] << " " << u[i][2] << "\n";
				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)) {
					// cout << "after1 " << edges[u[i][0]][1] << " " << edges[u[i][0]][2] << "\n";
					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
					// cout << "after2 " << edges[u[i][0]][1] << " " << edges[u[i][0]][2] << "\n";
					dsu.merge(edges[u[i][0]][1], edges[u[i][0]][2]);
					cnt++;
				}
				// cout << edges[u[i][0]][0] << "\n";
				// cout << (u[i][2] > ind) << " " << (!i or u[i - 1][0] != u[i][0]) << " " << (edges[u[i][0]][0] >= val) << "\n";
			}
			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:102: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]
  102 |    for(int i = 0; i < u.size(); i++) { // edge, w, ind
      |                   ~~^~~~~~~~~~
bridges.cpp:104: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]
  104 |     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)) {
      |                                              ~~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...