Submission #1045711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045711		NotLinux	Bridges (APIO19_bridges)	C++17	0 / 100	3046 ms	6320 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 = 316;
struct DSU{
	int par[N] , sz[N];
	void init(){
		iota(par , par + N , 0);
		fill(sz , sz + N , 1);
	}
	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;
	for(int i = 0;i<m;i++){
		int a,b,c;
		cin >> a >> b >> c;
		edges.push_back({c , a , b});// weight a b
	}
	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));
	for(int i = 0;i<sz(queries);i+=SQRT){
		// unchanged edges
		set < array < int , 3 > > 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.insert(edges[queries[j][1] - 1]);
			}
			else{
				query_sorted.push_back({queries[j][2] , queries[j][1] , j});
			}
		}
		vector < array < int , 3 > > unchanged;
		map < pair < int , int > , int > current_weights , bruh;
		vector < pair < int , int > > changed_edges;
		for(int j = 0;j<sz(edges);j++){
			if(changed.count(edges[j]) == 0){// degismicek
				unchanged.push_back(edges[j]);
			}
			else{//degiscek
				current_weights[{edges[j][1] , edges[j][2]}] = edges[j][0];
				// cout << "changed1 : " << edges[j][1] << " , " << edges[j][2] << " , weight : " << current_weights[{edges[j][1] , edges[j][2]}] << endl;
				changed_edges.push_back({edges[j][1] , edges[j][2]});
			}
		}
		bruh = current_weights;
		sort(all(unchanged));
		reverse(all(unchanged));
		sort(all(query_sorted));
		reverse(all(query_sorted));
		DSU dsu;
		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;
			// 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
			for(int j = i;j<indx;j++){
				if(queries[j][0] == 1){
					current_weights[{edges[queries[j][1] - 1][1] , edges[queries[j][1] - 1][2]}] = queries[j][2];
					// cout << "changed2 : " << edges[queries[j][1] - 1][1] << " , " << edges[queries[j][1] - 1][2] << " , weight : " << current_weights[{edges[queries[j][1] - 1][1] , edges[queries[j][1] - 1][2]}] << endl;
				}
			}
			int sayac = 0;
			for(auto itr : changed_edges){
				// cout << "changed : " << itr.first << " , " << itr.second << " , weight : " << current_weights[itr] << endl;
				if(current_weights[itr] >= val){
					dsu.merge(itr.first , itr.second);
					sayac++;
				}
			}
			ans[indx] = dsu.sz[dsu.find(node)];
			// cout << "ANS : " << ans[indx] << endl;
			for(int j = 0;j<sayac;j++){
				dsu.rollback();
			}
			current_weights = bruh;
		}
	}
	for(int i = 0;i<q;i++){
		if(ans[i] != -1){
			cout << ans[i] << '\n';
		}
	}
	cout << endl;
}
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: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27