Submission #1070688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070688		Tozzyyyy	Bridges (APIO19_bridges)	C++17	100 / 100	2630 ms	13920 KiB

bridges

#include<bits/stdc++.h>
#define all(x) (x).begin() , (x).end()
#define pll pair<long long, long long>
#define pii pair<int , int>
#define fi first
#define se second
#define bit(i,j) ((j >> i) & 1)
using namespace std;
 
const long long inf = 1e18;
const int MAXN = 1e6+100;
const int mod = 1e9+7;
 
struct edge{
	int u , v , w;
};
struct query{
	int type , a , b;
};
int ans[MAXN] , par[MAXN] , sz[MAXN];
vector<pair<int & , int>> his;
 
int find(int x) { return x == par[x] ? x : find(par[x]); }
 
void join(int a , int b){
	a = find(a) ; 
	b = find(b);
	if(a == b) return ;	
	if(sz[a] < sz[b]) swap(a , b);
 
	his.push_back({sz[a] , sz[a]});
	his.push_back({par[b] , par[b]});
 
	par[b] = a;
	sz[a] += sz[b];
}
 
void roll_back(int until){
	while(his.size() > until){
		his.back().first = his.back().second;
		his.pop_back();
	}
}
int32_t main(){
  	//freopen("B.inp", "r", stdin);
	//freopen("B.out", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);
 
	int n , m; cin >> n >> m;
	vector<edge> E(m + 1);
	for(int i = 1 ; i <= m ; i++){
		int x , y , w; cin >> x >> y >> w;
		E[i] = {x , y , w};
	}
	const int block = 500;
	int q; cin >> q;
	vector<query> Q(q+1);
	for(int i = 1 ; i <= q ; i++){
		cin >> Q[i].type >> Q[i].a >> Q[i].b;
	}
	for(int bl = 1 ; bl <= q / block + (q % block != 0) ; bl++){
		vector<int> b(m + 1) , un_change , change, g;
		vector<query> ask;
		his.clear();
		for(int i = 1 ; i <= n ; i++) sz[i] = 1 , par[i] = i;
		for(int i = (bl - 1) * block + 1 ; i <= min(bl * block , q) ; i++){
			if(Q[i].type == 1) b[Q[i].a] = -1 , change.push_back(i);
			else{
				ask.push_back({i , Q[i].b , Q[i].a});
			}
		}
		for(int i = 1 ; i <= m ; i++){
			if(b[i] == 0) un_change.push_back(i);
			else g.push_back(i);
		}
		sort(all(ask) , [&](query x , query y){
			return x.a > y.a;
		});
		sort(all(un_change) , [&](int x , int y){
			return E[x].w > E[y].w;
		});
		int j = 0;
		for(int i = 0 ; i < ask.size() ; i++){
			while(j < un_change.size() && E[un_change[j]].w >= ask[i].a){
				join(E[un_change[j]].u , E[un_change[j]].v); j++;
			}
			int cnt = his.size();
			
			for(int k = 0; k < change.size() ; k++){
				if(change[k] < ask[i].type){
					b[Q[change[k]].a] = Q[change[k]].b;
				}else break;
			}
			for(int k = 0; k < g.size() ; k++){
				int id = g[k];
				if(b[id] == -1){
					if(E[id].w >= ask[i].a) join(E[id].u , E[id].v);
				}else{
					if(b[id] >= ask[i].a) join(E[id].u , E[id].v);
					b[id] = -1;
				}
			}
			
			ans[ask[i].type] = sz[find(ask[i].b)];
			roll_back(cnt);
		}
		for(int k = 0; k < change.size() ; k++){
			E[Q[change[k]].a].w = Q[change[k]].b;
		}
		
	}
	for(int i = 1 ; i <= q ; i++){
		if(Q[i].type == 2) cout << ans[i] << "\n";
	}
 
 
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void roll_back(int)':
bridges.cpp:39:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int&, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |  while(his.size() > until){
      |        ~~~~~~~~~~~^~~~~~~
bridges.cpp: In function 'int32_t main()':
bridges.cpp:83:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for(int i = 0 ; i < ask.size() ; i++){
      |                   ~~^~~~~~~~~~~~
bridges.cpp:84:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |    while(j < un_change.size() && E[un_change[j]].w >= ask[i].a){
      |          ~~^~~~~~~~~~~~~~~~~~
bridges.cpp:89:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |    for(int k = 0; k < change.size() ; k++){
      |                   ~~^~~~~~~~~~~~~~~
bridges.cpp:94:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |    for(int k = 0; k < g.size() ; k++){
      |                   ~~^~~~~~~~~~
bridges.cpp:107:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |   for(int k = 0; k < change.size() ; k++){
      |                  ~~^~~~~~~~~~~~~~~

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