Submission #684221

#	Time	Username	Problem	Language	Result	Execution time	Memory
684221		radal	Bridges (APIO19_bridges)	C++17	100 / 100	2552 ms	11416 KiB

bridges

#include <bits/stdc++.h>
//#pragma GCC target("sse,sse2,avx2")
//#pragma GCC optimize("unroll-loops,O3")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
constexpr int N = 2e5+10,mod = 1e9+7,sq = 1500;
constexpr ll inf = 1e18+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}

vector<pll> e;
int W[N];
int par[N],sz[N],ans[N],lst[N];
bitset<N> mark;
vector<pair<int,pll> > Q;
vector<int> ve,pors,ch;
stack<int> st;

int getpar(int v){
	if (v == par[v]) return v;
	return getpar(par[v]);
}

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

bool cmp2(int i,int j){
	return (Q[i].Y.Y > Q[j].Y.Y);
}

bool mg(int i){
	int u = e[i].X,v = e[i].Y;
	int p1 = getpar(u),p2 = getpar(v);
	if (p1 == p2) return 0;
	if (sz[p2] < sz[p1]) swap(p2,p1);
	par[p1] = p2;
	sz[p2] += sz[p1];
	st.push(p1);
	return 1;
}

void undo(){
	int u = st.top();
	st.pop();
	sz[par[u]] -= sz[u];
	par[u] = u;
}


int main(){
	ios :: sync_with_stdio(0); cin.tie(0);  cout.tie(0);
	int n,m;
	cin >> n >> m;
	rep(i,0,m){
		int u,v,w;
		cin >> u >> v >> w;
		e.pb({u,v});
		W[i] = w;
	}
	int q;
	cin >> q;
	rep(i,0,q){
		int t,u,v;
		cin >> t >> u >> v;
		if (t == 1) u--;
		Q.pb({t,{u,v}});
	}
	for (int l = 0; l < q; l += sq){
		int r = min(l+sq,q);
		pors.clear();
		ve.clear();
		ch.clear();
		mark.reset();
		rep(i,l,r){
			if (Q[i].X == 1) mark[Q[i].Y.X] = 1;
			else pors.pb(i);
		}
		rep(i,0,m){
		   	if (!mark[i]) ve.pb(i);
			else{
			   	ch.pb(i);
				lst[i] = W[i];
			}
		}
		sort(all(ve),cmp);
		sort(all(pors),cmp2);
		while (!st.empty()) st.pop();
		rep(i,1,n+1){
			par[i] = i;
			sz[i] = 1;
		}
		int p = 0;
		for (int i : pors){
			for (int j : ch) lst[j] = W[j];
			while (p < (int)ve.size() && W[ve[p]] >= Q[i].Y.Y){
				mg(ve[p]);
				p++;
			}
			int t = 0;
			rep(j,l,i){
				if (Q[j].X == 2) continue;
				lst[Q[j].Y.X] = Q[j].Y.Y;
			}
			for (int j : ch) if (lst[j] >= Q[i].Y.Y){
				t += mg(j);
			}
			ans[i] = sz[getpar(Q[i].Y.X)];
			while (t--) undo();
		}
		rep(i,l,r) if (Q[i].X == 1) W[Q[i].Y.X] = Q[i].Y.Y;
	}
	rep(i,0,q) if (Q[i].X == 2) cout << ans[i] << 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