Submission #318285

#	Time	Username	Problem	Language	Result	Execution time	Memory
318285		kostia244	Bridges (APIO19_bridges)	C++17	0 / 100	3092 ms	14012 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 = 12;
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;
   	//cout << q << endl;
    for(int l = 0; l < q; l+=B) {
		memset(touch, -1, sizeof touch);
		int r = min(q, l+B);
       	vector<array<int, 3>> todo;
       	vector<int> touched;
       	sort(all(edges), [&](auto &I, auto &J) { int i = weights[I[3]].back()[1], j = weights[J[3]].back()[1]; return i < j || (i == j && I[3] < J[3]); });
    	for(int t, a, b, i = l; i < r; i++) {
			cin >> t >> a >> b;
			//cout << t << " " << a << " " << b << endl;
       		b *= -1;
       		//cout << i << " T IS EQUAL TO " << t << " FFS " << a << " " << b<< endl;
       		if(t == 1) {
				//cout << "BIG A " << a << endl;
       			if(touch[a] != 1+l) touched.push_back(old[a]);
       			touch[a] = 1+l;
       			weights[a].push_back({i, b});
       		} else {
       			a--;
       			todo.push_back({b, a, i});
       		}
       	}
       	sort(all(todo));
       	sort(all(touched), [&](auto &i, auto &j) { return get_weight(i, q) < get_weight(j, q) || (get_weight(i, q) == get_weight(j, q) && i < j); });
       	touched.erase(unique(all(touched)), touched.end());
       	dsu d(n);
       //	cout << l << endl;
       	{int lst = -(1<<30), tmp = 0;
       	for(auto &[u, w, U, i] : edges) {if(touch[i] != 1+l) {
			//cout << i << " ! " << touch[i] << endl;
			//cout << lst <<  " " << get_weight(tmp, q) << endl;
			assert(lst <= get_weight(tmp, q));
			
			lst = get_weight(tmp, q);
			
		}tmp++;}
		}
       	vector<int> te;
       	{
			vector<int> P;
			for(int i = 0; i < m; i++) P.push_back(edges[i][3]);
			sort(all(P));
			for(int i = 0; i < m; i++) assert(P[i] == i+1);
		}
       	for(int i = 0; i < m; i++) {if(touch[edges[i][3]] != 1+l) te.push_back(i);
			else {
				int ok = 0;
				for(auto &I : touched) ok |= i == I;
				assert(ok);
			}
		}
       	for(int j = 0, I = 0; I < todo.size(); I++) {
       		int t = todo[I][2], w = todo[I][0], v = todo[I][1];
       		j = 0;d = dsu(n);
      		while(j < m) {
       			if(touch[edges[j][3]] == 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;
       	tmp = 0;

    	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;
       	sort(all(edges_new), [&](auto &I, auto &J) { int i = weights[I[3]].back()[1], j = weights[J[3]].back()[1]; return i < j || (i == j && I[3] < J[3]); });

    	tmp = 0;
    	int lst = -(1<<30);
    	for(auto &[x, y, z, old_id] : edges) {
			old[old_id] = tmp++;
			assert(lst <= weights[old_id].back()[1]);
		}
		if(edges.size() < m) exit(47);
   	}
  	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:111:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for(int j = 0, I = 0; I < todo.size(); I++) {
      |                               ~~^~~~~~~~~~~~~
bridges.cpp:129:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |      while(i < te.size() || j < touched.size()) {
      |            ~~^~~~~~~~~~~
bridges.cpp:129:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |      while(i < te.size() || j < touched.size()) {
      |                             ~~^~~~~~~~~~~~~~~~
bridges.cpp:130:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |       if(i < te.size() && (j == touched.size() || get_weight(te[i], q) < get_weight(touched[j], q))) {
      |          ~~^~~~~~~~~~~
bridges.cpp:130:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |       if(i < te.size() && (j == touched.size() || get_weight(te[i], q) < get_weight(touched[j], q))) {
      |                            ~~^~~~~~~~~~~~~~~~~
bridges.cpp:143:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  143 |   if(edges.size() < m) exit(47);
      |      ~~~~~~~~~~~~~^~~

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