Submission #318245

#	Time	Username	Problem	Language	Result	Execution time	Memory
318245		kostia244	Bridges (APIO19_bridges)	C++17	14 / 100	2494 ms	13964 KiB

bridges

#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int maxn = 101100, B = 400;
int n, m, q, old[maxn], touch[maxn], ans[maxn];
vector<array<int, 4>> edges;
vector<array<int, 2>> weights[maxn];
struct dsu {
   	vector<int> r, p, rb;
   	dsu(int n = 0) : r(n, 1), p(n) { iota(all(p), 0); }
   	int par(int v) {
   		if(p[v] == v) return v;
   		return par(p[v]);
   	}
   	void unite(int i, int j) {
   		i = par(i), j = par(j);
   		rb.push_back(-1);
   		if(i == j) return;
   		if(r[i] < r[j]) swap(i, j);
   		p[j] = i;
   		r[i] += r[j];
   		rb.push_back(j);
   	}
   	void roll_back(int c) {
   		while(c--) {
   			int v = rb.back(); rb.pop_back();
   			if(v == -1) continue;
   			r[p[v]] -= r[v];
   			p[v] = v;
   		}
   	}
};
int get_weight(int e, int t) {
   	e = edges[e][3];
   	int i = weights[e].size()-1;
   	while(weights[e][i][0] > t) {
		i--;
	}
 	return weights[e][i][1];
}
int main() {
   	cin.tie(0)->sync_with_stdio(0);
   	cin >> n >> m;
   	edges.resize(m);
   	int tmp = 1;
   	for(auto &[x, y, z, old_id] : edges) {
   		cin >> x >> y >> z, x--, y--, old_id = tmp++;
   		z *= -1;
   	}
   	sort(all(edges), [](auto &a, auto &b) { return a[2] < b[2]; });
   	tmp = 0;
   	for(auto &[x, y, z, old_id] : edges) {
   		weights[old_id].push_back({-1, z});
   		old[old_id] = tmp++;
   	}
   	
   	memset(ans, -1, sizeof ans);
   	cin >> q;
   	for(int l = 0; l < q; l+=B) {
   		int r = min(q, l+B);
   		vector<array<int, 3>> todo;
   		vector<int> touched;
   		for(int t, a, b, i = l; i < r; i++) {
   			cin >> t >> a >> b;
   			b *= -1;
   			if(t == 1) {
   				touch[old[a]] = 1+l;
   				weights[a].push_back({i, b});
   				touched.push_back(old[a]);
   			} else {
   				a--;
   				todo.push_back({b, a, i});
   			}
   		}
   		sort(all(todo));
   		dsu d(n);
   		for(int j = 0, I = 0; I < todo.size(); I++) {
   			int t = todo[I][2], w = todo[I][0], v = todo[I][1];
  			while(j < m) {
   				if(touch[j] == 1+l) {j++; continue;}
   				if(get_weight(j, q) > w) break;
   				d.unite(edges[j][0], edges[j][1]);
   				j++;
			}
   			int rb = 0;
   			for(auto i : touched) if(get_weight(i, t) <= w) rb++, d.unite(edges[i][0], edges[i][1]);
   			ans[t] = d.r[d.par(v)];
   			d.roll_back(rb);
   		}
   		vector<array<int, 4>> edges_new;
   		vector<int> te;
   		tmp = 0;
   		sort(all(touched), [&](auto &i, auto &j) { return get_weight(i, q) < get_weight(j, q); });
   		for(auto &i : edges) {if(touch[tmp] != 1+l) te.push_back(tmp); tmp++;}
   		
   		{
		int lst = -1;
   		for(auto &i : touched) {
			if(lst != -1) assert(get_weight(lst, q) <= get_weight(i, q));
			lst = i;
		}
		}
   		
		int i = 0, j = 0;
		while(i < te.size() || j < touched.size()) {
			if(i < te.size() && (j == touched.size() || get_weight(te[i], q) < get_weight(touched[j], q))) {
				edges_new.push_back(edges[te[i++]]);
			} else edges_new.push_back(edges[touched[j++]]);
		}
		edges = edges_new;
		tmp = 0;
		for(auto &[x, y, z, old_id] : edges) {
			old[old_id] = tmp++;
		}
		//for(int i = 1; i < n; i++) assert(get_weight(i-1, q) <= get_weight(i, q));
   	}
   	for(int i = 0; i < q; i++) if(ans[i] >= 0) cout << ans[i] << '\n';
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:78:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |      for(int j = 0, I = 0; I < todo.size(); I++) {
      |                            ~~^~~~~~~~~~~~~
bridges.cpp:95:16: warning: unused variable 'i' [-Wunused-variable]
   95 |      for(auto &i : edges) {if(touch[tmp] != 1+l) te.push_back(tmp); tmp++;}
      |                ^
bridges.cpp:106:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   while(i < te.size() || j < touched.size()) {
      |         ~~^~~~~~~~~~~
bridges.cpp:106:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   while(i < te.size() || j < touched.size()) {
      |                          ~~^~~~~~~~~~~~~~~~
bridges.cpp:107:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |    if(i < te.size() && (j == touched.size() || get_weight(te[i], q) < get_weight(touched[j], q))) {
      |       ~~^~~~~~~~~~~
bridges.cpp:107:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |    if(i < te.size() && (j == touched.size() || get_weight(te[i], q) < get_weight(touched[j], q))) {
      |                         ~~^~~~~~~~~~~~~~~~~

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