Submission #255127

#	Time	Username	Problem	Language	Result	Execution time	Memory
255127		Atalasion	Bridges (APIO19_bridges)	C++14	30 / 100	3087 ms	6800 KiB

bridges

//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")


using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 100000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;
const int SQ = 160;
struct tagh{
	int v, SZ;
};
vector<tagh> Ch;

struct query{
	int id, v, w;
};

int n, m, q, W[N], E[N], V[N], U[N], par[N], sz[N], w[N], ans[N], mark[N], mark2[N];
vector<query> L[N];
pair<int, pii> Q[N];

bool cmp(int x, int y){
	return W[x] > W[y];
}

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

inline void merge(int v, int u){
	v = getpar(v), u = getpar(u);
	if (v == u) return;
	if (sz[v] < sz[u]) swap(v, u);
	tagh res;
	res.v = u;
	res.SZ = sz[u];
	Ch.pb(res);
	res.v = v;
	res.SZ = sz[v];
	Ch.pb(res);
	sz[v] += sz[u];
	par[u] = v;

}

inline void Solve(query q, int l, int r){
	vector<int> edge;
	for (int i = q.id; i >= l; i--){
		if (Q[i].F == 1){
			if (!mark2[Q[i].S.F]){
				w[Q[i].S.F] = Q[i].S.S, mark2[Q[i].S.F] = 1;
				if (w[Q[i].S.F] >= q.w) edge.pb(Q[i].S.F);
			}
		}
	}
	for (int i = q.id; i < r; i++){
		if (Q[i].F == 1){
			if (!mark2[Q[i].S.F]){
				mark2[Q[i].S.F] = 1;
				if (W[Q[i].S.F] >= q.w) edge.pb(Q[i].S.F);
			}
		}
	}
	Ch.clear();
	for (int i = l; i <= r; i++) mark2[Q[i].S.F] = 0;
	for (auto u:edge){
		merge(V[u], U[u]);
	}
	ans[q.id] = sz[getpar(q.v)];
	reverse(all(Ch));
	for (auto u:Ch){
		par[u.v] = u.v;
		sz[u.v] = u.SZ;
	}
	Ch.clear();
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int v,u, w;
		cin >> v >> u >> w;
		E[i] = i;
		W[i] = w;
		V[i] = v;
		U[i] = u;
	}
	sort(E + 1, E + m + 1, cmp);
	cin >> q;
	for (int i = 0; i< q; i++){
		sort(E + 1, E + m + 1, cmp);
		memset(mark, 0, sizeof mark);
		if (i * SQ >= q) break;
		for (int j = 0; j <= m; j++) L[j].clear(), L[j].shrink_to_fit();
		for (int j = i * SQ; j < min(q, (i + 1) * SQ); j++){
			int t, v, u;
			cin >> t >> v >> u;
			Q[j] = {t, {v, u}};
			if (t == 2){
				int l = 0, r = m + 1;
				while (r - l > 1){
					int md = (l + r) >> 1;
					if (W[E[md]] < u) r = md;
					else l = md;
				}
				query q;
				q.id = j;
				q.v = v;
				q.w = u;
				L[l].pb(q);
//				cout << l << '\n';
			}else{
				mark[v] = 1;
			}
		}
		for (int j = 1; j <= n; j++) par[j] = j, sz[j] = 1;
		for (int j = 0; j <= m; j++){
			if (!mark[E[j]]){
//				cout << "E " << V[E[j]] << ' ' << U[E[j]] << '\n';
				merge(V[E[j]], U[E[j]]);
			}
			for (auto u:L[j]){
				Solve(u, i * SQ, min(q, (i + 1) * SQ));
			}
		}
		for (int j = i * SQ; j < min(q, (i + 1) * SQ); j++) if(Q[j].F == 1) W[Q[j].S.F] = Q[j].S.S;
	}
	for (int i = 0; i < q; i++){
		if (Q[i].F == 2) cout << ans[i] << '\n';
	}







	return 0;
}

/*
7 8
1 2 5
1 6 5
2 3 5
2 7 5
3 4 5
4 5 5
5 6 5
6 7 5
5
2 1 6
1 1 1
2 1 2
1 2 3
2 2 2
*/

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