Submission #1143410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143410		SmuggingSpun	다리 (APIO19_bridges)	C++17	30 / 100	3094 ms	4664 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 = 140;
	const int N = 5e4 + 5;
	const int M = 1e5 + 5;
	int u[M], v[M], w[M], ans[M], init[M], parent[N], siz[N];
	bitset<M>changed;
	vector<int>cache;
	int find_set(int N){
		while(N != parent[N]){
			N = 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];
			cache.emplace_back(b);
		}
	}
	void roll_back(){
		int b = cache.back();
		cache.pop_back();
		siz[parent[b]] -= siz[b];
		parent[b] = b;	
	}
	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));
		memset(init, -1, sizeof(init));
		for(int l = 0; l < q; l += BASE){
			changed.reset();
			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 = 1; i <= m; i++){
				if(!changed.test(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 + 1, parent + n + 1, 1);
			fill(siz + 1, siz + n + 1, 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++;
				}
				for(int i = l; i < qi; i++){
					if(query[i].first > 0){
						if(init[query[i].first] == -1){
							init[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]);
					}
					if(init[i] != -1){
						w[i] = init[i];
						init[i] = -1;
					}
				}
				ans[qi] = siz[find_set(-query[qi].first)];
				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 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:161:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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