제출 #1049149

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1049149		NotLinux	다리 (APIO19_bridges)	C++17	100 / 100	2525 ms	11896 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
const int N = 5e4 + 7;
const int SQRT = 1000;
struct DSU{
	int par[N] , sz[N];
	void init(){
		iota(par , par + N , 0);
		fill(sz , sz + N , 1);
		while(sz(st))st.pop();
	}
	stack < pair < int , int > > st;
	void merge(int a , int b){
		a = find(a) , b = find(b);
		if(a == b)return;
		else if(sz[a] > sz[b])swap(a , b);
		sz[b] += sz[a];
		par[a] = par[b];
		st.push({a , b});
	}
	int find(int a){
		// cout << "find : " << a << " : " << par[a] << endl;
		if(par[a] == a)return a;
		else return find(par[a]);
	}
	void rollback(){
		assert(sz(st) > 0);
		pair < int , int > pai = st.top();
		st.pop();
		par[pai.first] = pai.first;
		sz[pai.second] -= sz[pai.first];
	}
};
void solve(){
	int n , m;
	cin >> n >> m;
	vector < array < int , 3 > > edges;
	vector < array < int , 3 > > queries;
	int bruh[m+1];
	for(int i = 0;i<m;i++){
		int a,b,c;
		cin >> a >> b >> c;
		edges.push_back({c , a , b});// weight a b
		bruh[sz(edges) - 1] = c;
	}
	int q;
	cin >> q;
	for(int i = 0;i<q;i++){
		int a,b,c;
		cin >> a >> b >> c;
		queries.push_back({a , b , c});
	}
	int ans[q];
	memset(ans , -1 , sizeof(ans));
	DSU dsu;
	for(int i = 0;i<sz(queries);i+=SQRT){
		// cout << "BLOCK : " << i << endl;
		// unchanged edges
		int changed[m];
		memset(changed , 0 , sizeof(changed));
		vector < array < int , 3 > > query_sorted;
		for(int j = i;j<(i + SQRT) and j < sz(queries);j++){
			if(queries[j][0] == 1){
				changed[queries[j][1] - 1] = 1;
			}
			else{
				query_sorted.push_back({queries[j][2] , queries[j][1] , j});
			}
		}
		vector < array < int , 3 > > unchanged;
		int current_weights[m+1];
		for(int i = 0;i<m;i++)current_weights[i] = bruh[i];
		vector < int > changed_edges;
		for(int j = 0;j<sz(edges);j++){
			if(changed[j] == 1){// degiscek
				changed_edges.push_back(j);
			}
			else{
				unchanged.push_back({current_weights[j] , edges[j][1] , edges[j][2]});
			}
		}
		sort(all(unchanged));
		reverse(all(unchanged));
		sort(all(query_sorted));
		reverse(all(query_sorted));
		dsu.init();
		int lp = 0;
		// cout << "dsu : ";for(int i = 1;i<=10;i++)cout << dsu.find(i) << " ";cout << endl;
		// cout << "unchanged : ";for(int i = 0;i<sz(unchanged);i++)cout << unchanged[i][0] << "," << unchanged[i][1] << "," << unchanged[i][2] << "   ";cout << endl;
		for(auto [val , node , indx] : query_sorted){
			// cout << "query : " << node << " , " << val << endl;
			for(int j = i;j<indx;j++){
				if(queries[j][0] == 1){
					current_weights[queries[j][1] - 1] = queries[j][2];
					// cout << "changed2 : " << edges[queries[j][1] - 1][1] << " , " << edges[queries[j][1] - 1][2] << " , weight : " << current_weights[queries[j][1] - 1] << endl;
				}
			}
			// unchanged
			while(lp < sz(unchanged) and unchanged[lp][0] >= val){
				// cout << "unchanged : " << unchanged[lp][1] << " , " << unchanged[lp][2] << " , weight : " << unchanged[lp][0] << endl;
				dsu.merge(unchanged[lp][1] , unchanged[lp][2]);
				lp++;
			}
			// changed
			int sayac = 0;
			for(auto itr : changed_edges){
				if(current_weights[itr] >= val and dsu.find(edges[itr][1]) != dsu.find(edges[itr][2])){
					// cout << "changed : " << edges[itr][1] << " , " << edges[itr][2] << " , weight : " << current_weights[itr] << endl;
					dsu.merge(edges[itr][1] , edges[itr][2]);
					sayac++;
				}
			}
			ans[indx] = dsu.sz[dsu.find(node)];
			// cout << "ANS : " << ans[indx] << endl;
			for(int j = 0;j<sayac;j++){
				dsu.rollback();
			}
			for(int i = 0;i<m;i++)current_weights[i] = bruh[i];
		}
		for(int j = i;j<(i + SQRT) and j < sz(queries);j++){
			if(queries[j][0] == 1){
				bruh[queries[j][1] - 1] = queries[j][2];
			}
		}
	}
	for(int i = 0;i<q;i++){
		if(ans[i] != -1){
			cout << ans[i] << '\n';
		}
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase=1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

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