Submission #258229

#	Time	Username	Problem	Language	Result	Execution time	Memory
258229		amoo_safar	Bridges (APIO19_bridges)	C++14	0 / 100	3062 ms	56708 KiB

bridges

// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const int N = 1e5 + 10;
const int Sq = 333;

int n, m, q;
int fr[N], to[N], w[N];
int t[N], a[N], b[N], ans[N];

int mk[N], Tmk = 1;
int mk2[N], Tmk2 = 1;

int par[N], sz[N];
int Find(int u){
	if(par[u] == u) return u;
	return par[u] = Find(par[u]);
}
void Unite(int u, int v){
	u = Find(u); v = Find(v);
	if(u == v) return ;
	par[u] = v;
	sz[v] += sz[u];
}

vector<int> Ws[N];

vector<int> E[N], Q[N], G[N];

int que[N], lq, rq;

void Solve(int l, int r){
	iota(par, par + n + 1, 0);
	fill(sz, sz + n + 1, 1);
	for(int i = 0; i < N; i++) E[i].clear();
	for(int i = 0; i < N; i++) Q[i].clear();
	Tmk ++;
	//////////////////
	for(int i = l; i < r; i++)
		if(t[i] == 1) mk[a[i]] = Tmk;

	for(int i = 1; i <= m; i++) if(mk[i] != Tmk) E[w[i]].pb(i);
	vector<int> C;
	for(int i = 1; i <= m; i++) if(mk[i] == Tmk) C.pb(i);

	for(int i = l; i < r; i++){
		if(t[i] == 1){
			w[a[i]] = b[i];
		}
		if(t[i] == 2){
			for(auto &x : C) Ws[i].pb(w[x]);
			Q[b[i]].pb(i);
		}
	}

	int ed;
	for(int W = N - 1; W >= 0; W--){
		for(auto &x : E[W]) Unite(fr[x], to[x]);
		for(auto &id : Q[W]){
			for(int i = 0; i < (int) C.size(); i++) G[ Find(fr[C[i]]) ].clear();
			for(int i = 0; i < (int) C.size(); i++) G[ Find(to[C[i]]) ].clear();

			for(int i = 0; i < (int) C.size(); i++){
				if(Ws[id][i] < W) continue;
				ed = C[i];
				G[Find(fr[ed])].pb(Find(to[ed]));
				G[Find(to[ed])].pb(Find(fr[ed]));
			}

			Tmk2 ++;

			lq = 0, rq = 1;
			que[0] = Find(a[id]);
			mk2[que[0]] = Tmk2;
			while(lq < rq){
				ans[id] += sz[que[lq]];

				for(auto &adj : G[que[lq]]){
					if(mk2[adj] != Tmk2){
						mk2[adj] = Tmk2;
						que[rq ++] = adj;
					}
				}
				lq ++;
			}
		}
	}


	/*
	for(int i = l; i < r; i++)
		if(t[i] == 1)
			w[a[i]] = b[i];
	*/
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	vector<int> V;
	for(int i = 1; i <= m; i++){
		cin >> fr[i] >> to[i] >> w[i];
		V.pb(w[i]);
	}
	cin >> q;
	for(int i = 1; i <= q; i++){
		cin >> t[i] >> a[i] >> b[i];
		if(t[i] == 1) V.pb(b[i]);	
	}

	sort(all(V)); V.resize(unique(all(V)) - V.begin());
	for(int i = 1; i <= m; i++)
		w[i] = lower_bound(all(V), w[i]) - V.begin();
	for(int i = 1; i <= q; i++)
		b[i] = lower_bound(all(V), b[i]) - V.begin();

	for(int i = 1; i <= q; i += Sq)
		Solve(i, min(q + 1, i + Sq));
	
	for(int i = 1; i <= q; i++) if(t[i] == 2) cout << ans[i] << '\n';
	return 0;
}

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