Submission #984904

#	Time	Username	Problem	Language	Result	Execution time	Memory
984904		Tsagana	Bridges (APIO19_bridges)	C++14	100 / 100	1544 ms	33448 KiB

bridges

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define pip pair<int, pii>
#define int long long
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define F first
#define S second

using namespace std;

struct Graph {
	int  n, m, q;
	int  sz[50005];
	int  dsu[50005];
	int  ans[100005];
	int  part = 1000;
	bool change[100005];
	vector<pip> edg;
	vector<pii> ord;
	vector<pip> query;
	vector<pii> bridge[1005];
	
	int find(int x) {return (dsu[x] == x ? x : find(dsu[x]));}
	void prepare() {
		for (int i = 1; i <= n; i++) {dsu[i] = i; sz[i] = 1;}
		for (int i = 0; i <  m; i++) {change[i] = 0;}
		ord.clear();
	}
	void join(int a, int b) {
		int pa = find(a), pb = find(b);
		if (pa == pb) return;
		if (sz[pa] < sz[pb]) swap(pa, pb);
		ord.pb({pa, pb}); dsu[pb] = pa; sz[pa] += sz[pb];
	}
	void undo(int szz) {
		while (ord.size() > szz) {
			int pa = ord.back().F, pb = ord.back().S; ord.pop_back();
			sz[pa] -= sz[pb]; dsu[pb] = pb;
		}
	} 
	void update(int st) {
		int en = min(st + part, q);
		prepare();
		vector<pip> qu, ed;
		vector<int> one;
		for (int i = st; i < en; i++) {
			if (query[i].F == 1) {change[query[i].S.F] = 1; one.pb(i);}
			else qu.pb({query[i].S.S, {query[i].S.F, i}});
		}
		for (int i = 0; i < m; i++) if (!change[i]) ed.pb(edg[i]);
		for (int i = st; i < en; i++) {
			if (query[i].F == 1) edg[query[i].S.F].F = query[i].S.S;
			else {
				bridge[i-st].clear();
				for (int q: one)
				if (edg[query[q].S.F].F >= query[i].S.S)
					bridge[i-st].pb(edg[query[q].S.F].S);
			}
		}
		sort(all(qu)); sort(all(ed));
		int e = ed.size()-1;
		for (int i = qu.size()-1; i >= 0; i--) {
			int w = qu[i].F;
			int land = qu[i].S.F;
			int idx = qu[i].S.S;
			while (e >= 0 && ed[e].F >= w)
			{join(ed[e].S.F, ed[e].S.S); e--;}
			int szz = ord.size();
			for (pii p: bridge[idx-st]) join(p.F, p.S);
			ans[idx] = sz[find(land)];
			undo(szz);
		}
	}
	void solve() {
		cin >> n >> m;
		for (int i = 0; i < m; i++)
		{int u, v, w; cin >> u >> v >> w; edg.pb({w, {u, v}});}
		cin >> q;
		for (int i = 0; i < q; i++) {
			int t, x, y; cin >> t >> x >> y;
			if (t == 1) x--;
			query.pb({t, {x, y}});
		}
		for (int st = 0; st < q; st += part) update(st);
		for (int i  = 0; i  < q; i++)
			if (query[i].F == 2) cout << ans[i] << '\n';
	}
} G;
signed main(){IOS G.solve(); return 0;}

Compilation message (stderr)

bridges.cpp: In member function 'void Graph::undo(long long int)':
bridges.cpp:43:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   43 |   while (ord.size() > szz) {
      |          ~~~~~~~~~~~^~~~~

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