Submission #1143390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143390		SmuggingSpun	Bridges (APIO19_bridges)	C++20	59 / 100	3092 ms	4152 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;
	void solve(){
		vector<int>u(m + 1), v(m + 1), w(m + 1);
		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;
			} 
		}
		vector<int>cache, parent(n + 1), siz(n + 1);
		auto find_set = [&] (int N){
			while(N != parent[N]){
				N = parent[N];
			}	
			return N;
		};
		auto 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];
				cache.emplace_back(b);
			}
		};
		auto roll_back = [&] (){
			int b = cache.back();
			cache.pop_back();
			siz[parent[b]] -= siz[b];
			parent[b] = b;	
		};
		vector<int>ans(q, -1);
		for(int l = 0; l < q; l += BASE){
			int r = min(q, l + BASE);
			vector<bool>changed(m + 1, false);
			vector<int>change, unchange, query_index;
			for(int i = l; i < r; i++){
				if(query[i].first > 0){
					if(!changed[query[i].first]){
						change.emplace_back(query[i].first);
						changed[query[i].first] = true;
					}
				}
				else{
					query_index.emplace_back(i);
				}
			}	
			for(int i = 1; i <= m; i++){
				if(!changed[i]){
					unchange.emplace_back(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.begin(), parent.end(), 0);
			fill(siz.begin(), siz.end(), 1);
			cache.clear();
			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++;
				}
				vector<pair<int, int>>cache_edge;
				for(int i = l; i < qi; i++){
					if(query[i].first > 0){
						cache_edge.emplace_back(query[i].first, w[query[i].first]);
						w[query[i].first] = query[i].second;
					}
				}
				int cache_time = cache.size();
				for(int& i : change){
					if(w[i] >= query[qi].second){
						merge(u[i], v[i]);
					}
				}
				ans[qi] = siz[find_set(-query[qi].first)];
				while(!cache_edge.empty()){
					auto [a, b] = cache_edge.back();
					cache_edge.pop_back();
					w[a] = b;
				}
				while(cache.size() > cache_time){
					roll_back();
				}
			}
			for(int i = l; i < r; i++){
				if(query[i].first > 0){
					w[query[i].first] = query[i].second;
				}
			}
		}
		for(int& x : ans){
			if(x != -1){
				cout << x << "\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:157:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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