Submission #884208

#	Time	Username	Problem	Language	Result	Execution time	Memory
884208		Hakiers	Bridges (APIO19_bridges)	C++17	100 / 100	1627 ms	12388 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1e5 + 7;
constexpr int SQRT = 1000;
struct edg{
	int u, v, w;
};
struct que{
	int t, x, y;
};
edg edges[MAXN];
que queries[MAXN];
int sajz[MAXN];
int rep[MAXN];
int res[MAXN];
vector<int> last[SQRT+1];
stack<int> S;
int n, m, q;

int Find(int a){
	if(a == rep[a]) return a;
	return Find(rep[a]);
}

void Union(int a, int b){
	a = Find(a);
	b = Find(b);
	if(a == b) return;
	if(sajz[a] < sajz[b]) swap(a, b);
	S.push(b);
	rep[b] = a;
	sajz[a] += sajz[b];
}

void roll_back(int x){
	while(S.size() > x){
		int b = S.top();
		S.pop();
		sajz[Find(b)] -= sajz[b];
		rep[b] = b;
	}
}

void resetdsu(){
	for(int i = 1; i <= n; i++){
		sajz[i] = 1;
		rep[i] = i;
	}
	while(S.size()) S.pop();
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
		cin >> edges[i].u >> edges[i].v >> edges[i].w;
	
	cin >> q;
	for(int i = 1; i <= q; i++)
		cin >> queries[i].t >> queries[i].x >> queries[i].y;
		
		
	for(int l = 1; l <= q; l += SQRT){
		int r = min(q, l + SQRT - 1);
		resetdsu();
		
		vector<bool> changed(m+1, false);
		vector<int> ans;
		vector<int> act;
		
		for(int i = l; i <= r; i++){
			if(queries[i].t == 1){
				changed[queries[i].x] = 1;
				act.push_back(queries[i].x);
			}
			else ans.push_back(i);
		}
		
		vector<int> unchanged;
		for(int i = 1; i <= m; i++)
			if(!changed[i]) unchanged.push_back(i);
		
		for(int i = l; i <= r; i++){
			if(queries[i].t == 1)
				edges[queries[i].x].w = queries[i].y;
			else{
				last[i-l].clear();
				last[i-l].shrink_to_fit();	
				for(auto z : act)
					if(edges[z].w >= queries[i].y) last[i-l].push_back(z);
			}
		}
		
		sort(unchanged.begin(), unchanged.end(), [&](int a, int b) { return edges[a].w > edges[b].w;});
		sort(ans.begin(), ans.end(), [&](int a, int b) { return queries[a].y > queries[b].y;});
		
		int it = 0;
		for(auto i : ans){
			while(it < unchanged.size() && edges[unchanged[it]].w >= queries[i].y){
				Union(edges[unchanged[it]].u, edges[unchanged[it]].v);
				++it;
			}
			int prev_lenght = S.size();
			
			for(auto z : last[i - l])
				Union(edges[z].u, edges[z].v);
			res[i] = sajz[Find(queries[i].x)];
			roll_back(prev_lenght);
		}
		
	}
	
	for(int i = 1; i <= q; i++)
		if(queries[i].t == 2) cout << res[i] << "\n";
}

Compilation message (stderr)

bridges.cpp: In function 'void roll_back(int)':
bridges.cpp:36:17: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |  while(S.size() > x){
      |        ~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:100:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |    while(it < unchanged.size() && edges[unchanged[it]].w >= queries[i].y){
      |          ~~~^~~~~~~~~~~~~~~~~~

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