Submission #318265

#TimeUsernameProblemLanguageResultExecution timeMemory
318265kostia244Bridges (APIO19_bridges)C++17
13 / 100
3076 ms10868 KiB
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int maxn = 101100, B = 10000;
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[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];
       		d = dsu(n);
       		for(int i = 0; i < m; i++) if(get_weight(i, t) <= w) d.unite(edges[i][0], edges[i][1]);
       		ans[t] = d.r[d.par(v)];
       	}
       	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[edges[tmp][3]] != 1+l) te.push_back(tmp); tmp++;}
    	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;
    	int lst = -(1<<30);
    	for(auto &[x, y, z, old_id] : edges) {
			old[old_id] = tmp++;
			assert(lst <= weights[old_id].back()[1]);
		}
   	}
  	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: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]
   78 |         for(int j = 0, I = 0; I < todo.size(); I++) {
      |                               ~~^~~~~~~~~~~~~
bridges.cpp:78:17: warning: unused variable 'j' [-Wunused-variable]
   78 |         for(int j = 0, I = 0; I < todo.size(); I++) {
      |                 ^
bridges.cpp:88:19: warning: unused variable 'i' [-Wunused-variable]
   88 |         for(auto &i : edges) {if(touch[edges[tmp][3]] != 1+l) te.push_back(tmp); tmp++;}
      |                   ^
bridges.cpp:90:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |      while(i < te.size() || j < touched.size()) {
      |            ~~^~~~~~~~~~~
bridges.cpp:90:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |      while(i < te.size() || j < touched.size()) {
      |                             ~~^~~~~~~~~~~~~~~~
bridges.cpp:91:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |       if(i < te.size() && (j == touched.size() || get_weight(te[i], q) < get_weight(touched[j], q))) {
      |          ~~^~~~~~~~~~~
bridges.cpp:91:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |       if(i < te.size() && (j == touched.size() || get_weight(te[i], q) < get_weight(touched[j], q))) {
      |                            ~~^~~~~~~~~~~~~~~~~
#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...