Submission #792831

#	Time	Username	Problem	Language	Result	Execution time	Memory
792831		phoenix0423	Bridges (APIO19_bridges)	C++17	0 / 100	34 ms	12548 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#pragma GCC target("popcnt")
#define pb push_back
const int N = 1e9 + 7;
const int maxn = 5e4 + 5;
//we need an edge list representation
ll u[maxn], v[maxn], w[maxn];
ll t[maxn], x[maxn], y[maxn], ch[maxn]; // [bridge, new weight] or [start, car weight]
ll ans[maxn];
vector<int> to_join[maxn];
int n, m, q;
const int b = 400;
struct dsu_save{
	int u, rku, v, rkv;
	dsu_save(){}
	dsu_save(int _u, int _rku, int _v, int _rkv) : u(_u), rku(_rku), v(_v), rkv(_rkv){}
};
struct DSU{
	vector<int> par, siz;
	int n;
	stack<dsu_save> stk;
	DSU(){}
	DSU(int _n) : n(_n){
		par.resize(n);
		siz.resize(n, 1);
		for(int i = 0; i < n; i++) par[i] = i;
	}
	int root(int x){
		return x == par[x] ? x : root(par[x]);
	}
	void unite(int x, int y){
		x = root(x);
		y = root(y);
		if(x == y) return;
		if(siz[x] > siz[y]) swap(x, y);
		stk.push(dsu_save(x, siz[x], y, siz[y]));
		par[x] = y;
		siz[y] += siz[x];
		siz[x] = 0;
	}
	void roll_back(int sz){
		while(stk.size() > sz){
			auto [u, rku, v, rkv] = stk.top(); stk.pop();
			siz[u] = rku;
			siz[v] = rkv;
			par[u] = u;
		}
	}
};
int main(void){

	fastio;
	cin>>n>>m;
	DSU dsu(n + 1);
	for(int i = 1; i <= m; i++){
		cin >> u[i] >> v[i] >> w[i];
	}
	cin>>q;
	for(int i = 1; i <= q; i++){
		cin >> t[i] >> x[i] >> y[i];
	}
	for(int l = 1; l <= q; l += b){
		int r = min(q + 1, l + b);
		fill(ch, ch + maxn, false);
		vector<int> ask, upd, unchanged;

		for(int i = l; i < r; i++){
			if(t[i] == 1){
				ch[x[i]] = true;
				upd.pb(i);
			}
			else ask.pb(i);
		}
		for(int i = 1; i <= m; i++){
			if(!ch[i]) unchanged.pb(i);
		}
		for(int i = l; i < r; i++){
			if(t[i] == 1) w[x[i]] = y[i];
			else{
				to_join[i].clear();
				for(auto j : upd){
					if(w[x[j]] >= y[i]) to_join[i].pb(x[j]);
				}
			}
		}
		sort(ask.begin(), ask.end(), [](int a, int b){ return y[a] > y[b];});
		sort(unchanged.begin(), unchanged.end(), [](int a, int b){ return w[a] > w[b];});
		// processing queries
		int unptr = 0;
		for(auto i : ask){
			while(unptr < unchanged.size() && w[unchanged[unptr]] >= y[i]){ // no need to roll back
				dsu.unite(u[unchanged[unptr]], v[unchanged[unptr]]);
				unptr++;
			}
			int prev_sz = dsu.stk.size();
			for(auto j : to_join[i]){
				dsu.unite(u[j], v[j]);
			}
			ans[i] = dsu.siz[dsu.root(x[i])];
			dsu.roll_back(prev_sz);
		}
	}
	for(int i = 1; i <= q; i++) if(t[i] == 2) cout << ans[i] << "\n";
}

Compilation message (stderr)

bridges.cpp: In member function 'void DSU::roll_back(int)':
bridges.cpp:46:20: warning: comparison of integer expressions of different signedness: 'std::stack<dsu_save>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |   while(stk.size() > sz){
      |         ~~~~~~~~~~~^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:95:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |    while(unptr < unchanged.size() && w[unchanged[unptr]] >= y[i]){ // no need to roll back
      |          ~~~~~~^~~~~~~~~~~~~~~~~~

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