Submission #1143419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143419		SmuggingSpun	Bridges (APIO19_bridges)	C++20	13 / 100	3088 ms	45708 KiB

bridges

#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
int n, m, q;
namespace sub1{
	void solve(){
		vector<int>u(m + 1), v(m + 1), w(m + 1);
		vector<vector<int>>g(n + 1);
		for(int i = 1; i <= m; i++){
			cin >> u[i] >> v[i] >> w[i];
			g[u[i]].emplace_back(i);
			g[v[i]].emplace_back(i);
		}
		cin >> q;
		for(int _ = 0; _ < q; _++){
			int _t, a, b;
			cin >> _t >> a >> b;
			if(_t == 1){
				w[a] = b;
			}
			else{
				vector<bool>vis(n + 1, false);
				vis[a] = true;
				queue<int>Q;
				Q.push(a);
				int ans = 1;
				while(!Q.empty()){
					int i = Q.front();
					Q.pop();
					for(int& index : g[i]){
						int j = u[index] ^ v[index] ^ i;
						if(w[index] >= b && !vis[j]){
							ans++;
							vis[j] = true;
							Q.push(j);
						}
					}
				}
				cout << ans << "\n";
			}
		}
	}
}
namespace sub23456{
	const int BASE = 300;
	const int N = 5e4 + 5;
	const int M = 1e5 + 5;
	int u[M], v[M], w[M], ans[M], parent[N], siz[N];
	bitset<M>changed;
	bitset<N>vis;
	vector<int>vertex, g[N], join[BASE];
	int find_set(int N){
		while(N != parent[N]){
			N = parent[N] = parent[parent[N]];
		}
		return N;
	}
	void merge(int a, int b){
		if((a = find_set(a)) != (b = find_set(b))){
			if(siz[a] < siz[b]){
				swap(a, b);
			}
			siz[parent[b] = a] += siz[b];
		}
	}
	void dfs(int s){
		vis[s] = true;
		vertex.emplace_back(s);
		for(int& d : g[s]){
			if(!vis[d]){
				dfs(d);
			}
		}
	}
	void solve(){
		for(int i = 1; i <= m; i++){
			cin >> u[i] >> v[i] >> w[i];
		}
		cin >> q;
		vector<pair<int, int>>query(q);	 
		for(auto& [a, b] : query){
			int _t;
			cin >> _t >> a >> b;
			if(_t == 2){
				a = -a;
			} 
		}
		memset(ans, -1, sizeof(ans));
		vis.reset();
		changed.reset();
		for(int l = 0; l < q; l += BASE){
			int r = min(q, l + BASE);
			vector<int>change, unchange, query_index;
			for(int i = l; i < r; i++){
				if(query[i].first > 0){
					if(!changed.test(query[i].first)){
						change.emplace_back(query[i].first);
						changed.set(query[i].first);
					}
				}
				else{
					query_index.emplace_back(i);
				}
			}	
			for(int i = l; i < r; i++){
				if(query[i].first > 0){
					w[query[i].first] = query[i].second;
				}
				else{
					query_index.emplace_back(i);
					join[i - l].clear();
					for(int& j : change){
						if(w[j] >= query[i].second){
							join[i - l].emplace_back(j);
						}
					}
				}
			}
			for(int i = 1; i <= m; i++){
				if(!changed.test(i)){
					unchange.emplace_back(i);
				}
				else{
					changed.reset(i);
				}
			}
			sort(unchange.begin(), unchange.end(), [&] (int i, int j) -> bool{
				return w[i] > w[j];
			});
			sort(query_index.begin(), query_index.end(), [&] (int i, int j) -> bool{
				return query[i].second > query[j].second;
			});
			iota(parent + 1, parent + n + 1, 1);
			fill(siz + 1, siz + n + 1, 1);
			int pfix = 0;
			for(int& qi : query_index){
				while(pfix < unchange.size() && w[unchange[pfix]] >= query[qi].second){
					merge(u[unchange[pfix]], v[unchange[pfix]]);
					pfix++;
				}
				for(int& i : join[qi - l]){
					g[find_set(u[i])].emplace_back(find_set(v[i]));
					g[find_set(v[i])].emplace_back(find_set(u[i]));
				}
				ans[qi] = 0;
				vertex.clear();
				dfs(find_set(-query[qi].first));
				for(int& i : vertex){
					ans[qi] += siz[i];
					vis[i] = false;
					g[find_set(u[i])].clear();
					g[find_set(v[i])].clear();
				}
			}
			for(int i = l; i < r; i++){
				if(query[i].first > 0){
					w[query[i].first] = query[i].second;
				}
			}
		}
		for(int i = 0; i < q; i++){
			if(ans[i] != -1){
				cout << ans[i] << "\n";
			}
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> m;
	if(n <= 1000 && m <= 1000){
		sub1::solve();
	}
	else{
		sub23456::solve();
	}
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:171:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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