제출 #1318365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318365		blackscreen1	다리 (APIO19_bridges)	C++20	14 / 100	1111 ms	9648 KiB

bridges

#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
ll n, m, q;
pair<ll, pll> a[100005], qu[100005];
bool used[100005];
const ll blk = 1000;
vector<pair<pll, ll>> cq;
vector<vector<ll>> cqu;
vector<ll> edi;
ll par[50005], sz[50005];
vector<pll> upds;
ll ans[100005];
pll edg[100005];
ll find(ll x) {
	return (x == par[x] ? x : find(par[x]));
}
void merge(ll x, ll y, bool sp) {
	x = find(x), y = find(y);
	if (x == y) return;
	if (sz[x] < sz[y]) swap(x, y);
	sz[x] += sz[y];
	par[y] = x;
	if (sp) upds.push_back({x, y});
}
void undo() {
	for (auto it : upds) {
		sz[it.first] -= sz[it.second];
		par[it.second] = it.second;
	}
	upds.clear();
}
ll id[100005];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	iloop(0, m) {
		cin >> a[i].second.first >> a[i].second.second >> a[i].first;
		a[i].second.first--, a[i].second.second--;
	}
	cin >> q;
	iloop(0, q) {
		cin >> qu[i].first >> qu[i].second.first >> qu[i].second.second;
		qu[i].second.first--;
	}
	iloop(0, (q + blk - 1)/blk) {
		ll cs = i*blk, ed = min((i+1)*blk, q);
		jloop(0, n) par[j] = j, sz[j] = 1;
		memset(used, 0, sizeof(used));
		edi.clear();
		cq.clear();
		cqu.clear();
		jloop(cs, ed) if (qu[j].first == 1) if (!used[qu[j].second.first]) {edi.push_back(qu[j].second.first); used[qu[j].second.first] = 1;}
		jloop(cs, ed) {
			if (qu[j].first == 1) {
				a[qu[j].second.first].first = qu[j].second.second;
			}
			else {
				//cout << j << ":";
				cq.push_back({{qu[j].second.second, qu[j].second.first}, j});
				id[j] = cqu.size();
				cqu.push_back({});
				for (auto it : edi) if (a[it].first >= qu[j].second.second) cqu.back().push_back(it);
				//cout << "\n";
			}
		}
		jloop(0, m) edg[j] = {a[j].first, j};
		sort(edg, edg + m, greater<pll>());
		ll ci = 0, t = cq.size();
		if (t) sort(cq.begin(), cq.end(), greater<pair<pll, ll>>());
		jloop(0, m) if (!used[edg[j].second]) {
			while (ci < t && cq[ci].first.first > edg[j].first) {
				for (auto it : cqu[id[cq[ci].second]]) {
					//cout << cq[ci].second << "," << it << "\n";
					merge(a[it].second.first, a[it].second.second, 1);
				}
				ans[cq[ci].second] = sz[find(cq[ci].first.second)];
				undo();
				ci++;
			}
			merge(a[edg[j].second].second.first, a[edg[j].second].second.second, 0);
		}
		while (ci < t) {
			for (auto it : cqu[id[cq[ci].second]]) merge(a[it].second.first, a[it].second.second, 1);
			ans[cq[ci].second] = sz[find(cq[ci].first.second)];
			undo();
			ci++;
		}
	}
	iloop(0, q) if (qu[i].first == 2) cout << ans[i] << "\n";
}

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