Submission #545483

#	Time	Username	Problem	Language	Result	Execution time	Memory
545483		Mazaalai	다리 (APIO19_bridges)	C++17	0 / 100	3040 ms	69752 KiB

bridges

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define ALL(x) x.begin(),x.end()
using namespace std;
using PII = pair <int, int>;
const int N = 5e4+5;
const int M = 1e5+5;
const int BLOCK = 320;
int n, m, k, q;
int u[M], v[M], w[M];
vector <int> join[BLOCK];
vector <int> updates, curQueries, unchanged;
bool changed[M];
// queries
int ans[M];
PII queries[M];
bool type[M], QUERY = 1;
// DSU
vector <int> stk;
int par[M], sz[M];
int find(int a) {
	while (par[a] != a) a = par[a];
	return a;
}
void merge(int a, int b) {
	int x, y;
	x = a, y = b;
	a = find(a);
	b = find(b);
	if (a == b) return;
	if (sz[a] < sz[b]) swap(a, b);
	// cout << "CONNECT: " << b << ' ' << a << '\n';
	sz[a] += sz[b];
	par[b] = a;
	stk.pb(b);
}
void rewind(int tar) {
	while(stk.size() > tar) {
		int cur = stk.back(); stk.pop_back();
		// cout << "DISCONNECT: " << cur << ' ' << par[cur] << '\n';
		sz[par[cur]] -= sz[cur];
		par[cur] = cur;
	}
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// freopen("0.in", "r", stdin);
	// freopen("0.out", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) 
		cin >> u[i] >> v[i] >> w[i];
	cin >> q;
	for (int i = 1; i <= q; i++) {
		int t; cin >> t >> queries[i].ff >> queries[i].ss;
		type[i] = (t != QUERY);
	}
	for (int l = 1; l <= q; l+=BLOCK) {
		int r = min(l+BLOCK-1, q);
		// reset
		updates.clear();
		unchanged.clear();
		curQueries.clear();
		fill(sz+1, sz+1+m, 1);
		iota(par+1, par+1+m, 1);
		memset(changed, 0, sizeof(changed));
		// solution
		for (int i = l; i <= r; i++) {
			if (type[i] == QUERY) {
				curQueries.pb(i);
			} else {
				changed[queries[i].ff] = 1;
				updates.pb(i);
			}
		}
		for (int i = 1; i <= m; i++) 
			if (!changed[i]) unchanged.pb(i);
		
		for (int i = l; i <= m; i++) {
			if (type[i] == QUERY) {
				for (auto el : updates)
					if (w[queries[el].ff] >= queries[i].ss) {
						join[i-l].pb(el);
						// cout << i-l+1 << " add " << el  << " from " << w[queries[el].ff] << "," << queries[el].ss << '\n';
					}
			} else {
				// cout << i << ' ' << "CHANGE: " << queries[i].ff << '\n';
				w[queries[i].ff] = queries[i].ss;
			}
		}
		sort(ALL(curQueries), [&](int a, int b) {return queries[a].ss > queries[b].ss;});
		sort(ALL(unchanged), [&](int a, int b) {return w[a] > w[b];});
		int pt = 0;
		// cout << "UNCHANGED: ";
		// for (auto el : unchanged) cout << el << ',' << w[el] << " "; cout << '\n';
		for (auto query : curQueries) {
			// cout << "--------------------\n";
			// cout << query << '\n';
			while(pt < unchanged.size() && w[unchanged[pt]] >= queries[query].ss) {
				// cout << "UNCHANGED " << unchanged[pt] << '\n' ;
				merge(u[unchanged[pt]], v[unchanged[pt]]); pt++;
			}
			int curSz = stk.size();
			for (auto el : join[query-l]) {
				// cout << "EDGE: " << queries[el].ff <<  " -> ";
				merge(u[queries[el].ff], v[queries[el].ff]);
			}
			// cout << "ANSWER: " << query << ' ' << queries[query].ff << ',' << queries[query].ss << '\n';
			ans[query] = sz[find(queries[query].ff)];
			rewind(curSz);
		}
	}

	for (int i = 1; i <= q; i++) 
		if (type[i] == QUERY) cout << ans[i] << "\n";
}

Compilation message (stderr)

bridges.cpp: In function 'void merge(int, int)':
bridges.cpp:28:6: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   28 |  int x, y;
      |      ^
bridges.cpp:28:9: warning: variable 'y' set but not used [-Wunused-but-set-variable]
   28 |  int x, y;
      |         ^
bridges.cpp: In function 'void rewind(int)':
bridges.cpp:40:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |  while(stk.size() > tar) {
      |        ~~~~~~~~~~~^~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:102:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |    while(pt < unchanged.size() && w[unchanged[pt]] >= queries[query].ss) {
      |          ~~~^~~~~~~~~~~~~~~~~~

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