Submission #933991

#	Time	Username	Problem	Language	Result	Execution time	Memory
933991		vjudge1	Bridges (APIO19_bridges)	C++17	100 / 100	2123 ms	17620 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define N 50005
#define blsiz 800
#define M 100005

int n, m, q, u[M], v[M], w[M], t[M], vq[M], wq[M], si[N], par[N], check[M], res[M];
vector<int> newe, olde, gt[blsiz + 5], vex;
stack<int> st;

void reset(){
	for (int i = 1; i <= n; i++){
		par[i] = i;
		si[i] = 1;
	}
	for (int i = 1; i <= m; i++) check[i] = 0;
	newe.clear();
	olde.clear();
	vex.clear();
	while (st.size()) st.pop();
	for (int i = 0; i <= blsiz; i++) gt[i].clear();
}

void back(int siz){
	while ((int) st.size() > siz){
		int u = st.top();
		st.pop();
		si[par[u]] -= si[u];
		par[u] = u;
	}
}

int find(int u){
	if (u == par[u]) return u;
	return find(par[u]);
}

void unin(int u, int v){
	u = find(u);
	v = find(v);
	if (u == v) return;
	if (si[u] < si[v]) swap(u, v);
	par[v] = u;
	si[u] += si[v];
	st.push(v);
}

bool cmp(int& i, int& j){
	return w[i] > w[j];
}

bool cmp2(int& i, int& j){
	return wq[i] > wq[j];
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
        
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
    	cin >> u[i] >> v[i] >> w[i];
    }	
    cin >> q;
    for (int i = 1; i <= q; i++){
    	cin >> t[i] >> vq[i] >> wq[i];
    }

    for (int l = 1; l <= q; l += blsiz){
    	int r = min(q, l + blsiz - 1);
    	reset();
    	for (int i = l; i <= r; i++){
    		if (t[i] == 1 && !check[vq[i]]){
    			check[vq[i]] = 1;
    			newe.push_back(i);
    		}
    	}
    	for (int i = 1; i <= m; i++){
    		if (check[i]) continue;
    		olde.push_back(i);
    	}
    	for (int i = l; i <= r; i++){
    		vex.push_back(i);
    		if (t[i] == 1){
    			w[vq[i]] = wq[i];
    			continue;
    		}
    		for (auto x : newe){
    			if (w[vq[x]] >= wq[i]) gt[i - l].push_back(vq[x]);
    		}
    	}
    	sort(olde.begin(), olde.end(), cmp);
    	sort(vex.begin(), vex.end(), cmp2);
    	int j = -1;
    	for (auto x : vex){
    		if (t[x] == 1) continue;
    		while (j + 1 < (int)olde.size() && wq[x] <= w[olde[j + 1]]){
    			j++;
    			unin(u[olde[j]], v[olde[j]]);
    		}
    		int lastsiz = (int) st.size();
    		for (auto xx : gt[x - l]){
    			//if (w[xx] >= wq[x]){
    			unin(u[xx], v[xx]);
    		}
    		res[x] = si[find(vq[x])];
    		back(lastsiz);
    	}
    }

    for (int i = 1; i <= q; i++){
    	if (t[i] == 2) cout << res[i] << "\n";
    }
//l

    return 0;
}     

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