Submission #1098627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098627		flyingkite	Bridges (APIO19_bridges)	C++17	100 / 100	2432 ms	11360 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
 
#define ll int
#define pll pair<int, int>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 3e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 350;
ll n,m,q;
struct edge{ll u,v,c,idx;} e[N], b[N];
struct query{ll typ,x,y;} t[N];
struct ccjv{ll s,w,idx;};
ll cnt[N], res[N], used[N], cost[N], mn[N];
struct dsu{
	ll n;
	struct snap{ll v, u, lst_par, lst_sz;};
	vector<ll>p, sz;
	vector<snap>g;
	void init(ll _n){
		n = _n;
		p.resize(n + 10); sz.resize(n + 10);
		g.clear();
		for(int i = 1; i <= n;i++) p[i] = i, sz[i] = 1;
	}
	ll find(ll v){
		return (v == p[v] ? v : find(p[v]));
	}
	void join(ll u, ll v){
		u = find(u), v = find(v);
		if(u == v) return;
		if(sz[u] < sz[v]) swap(u, v);
		g.pb({v, u, p[v], sz[u]});
		p[v] = u, sz[u] += sz[v];
	}
	void reset(){g.clear();}
	void roll_back(){
		while(g.size()){
			ll u = g.back().u, v = g.back().v, lst_par = g.back().lst_par, lst_sz = g.back().lst_sz;
			p[v] = lst_par, sz[u] = lst_sz;
			g.pop_back();
		}
	}
} dsu;
void to_thic_cau(){ 
	cin >> n >> m;
	for(int i = 1; i <= m;i++) {
		cin >> e[i].u >> e[i].v >> e[i].c;
		e[i].idx = i; cost[i] = e[i].c;
		b[i] = e[i];
	}
	cin >> q;
	for(int i = 1; i <= q;i++) cin >> t[i].typ >> t[i].x >> t[i].y;
	for(int i = 1; i <= q;i += block){
		sort(e + 1, e + m + 1, [&](const edge &a, const edge &b){
			return cost[a.idx] > cost[b.idx];
		});
		dsu.init(n);
		vector<ccjv>ask;
		vector<ll>c;
		for(int i = 1; i <= m;i++) used[i] = 0, mn[i] = inf;
		for(int j = i; j <= min(q, i + block - 1);j++){
			if(t[j].typ == 1) c.pb(j), used[t[j].x] = 1, mn[t[j].x] = min(mn[t[j].x], j);
			else ask.pb({t[j].x, t[j].y, j});
		}
		sort(all(ask), [&](const ccjv &a, const ccjv &b){
			return a.w > b.w;
		});
		sort(all(c), greater<ll>());
		ll j = 1;
		for(auto x : ask){
			ll u = x.s, w = x.w, idx = x.idx;
			while(j <= m && cost[e[j].idx] >= w){
				if(!used[e[j].idx]) {
					dsu.join(e[j].u, e[j].v);
				}
				j++;
			}
			dsu.reset();
			for(auto k : c){
				if(k > idx) continue;
				ll cur = t[k].x, val = t[k].y;
				if(used[cur] == 2) continue;
				used[cur] = 2;
				if(val >= w) {
					dsu.join(b[cur].u, b[cur].v);
				}
			};
			for(int dm = (ll)c.size() - 1; dm >= 0;dm--){
				ll k = c[dm];
				ll cur = t[k].x, val = t[k].y;
				if(mn[cur] > idx && used[cur] == 1 && cost[cur] >= w){
					used[cur] = 2;
					dsu.join(b[cur].u, b[cur].v);
				}  
			}
			for(auto k : c) used[t[k].x] = 1;
			res[idx] = dsu.sz[dsu.find(u)];
			dsu.roll_back();
		}
		for(int dm = (ll)c.size() - 1; dm >= 0;dm--){
			ll k = c[dm];
			cost[t[k].x] = t[k].y;	
		}
	}
	for(int i = 1; i <= q;i++) if(res[i]) cout << res[i] << '\n';
}     
 
 
signed main()   
{  
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

Compilation message (stderr)

bridges.cpp:12:16: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   12 | const ll inf = 1e18;
      |                ^~~~
bridges.cpp: In function 'void to_thic_cau()':
bridges.cpp:96:22: warning: unused variable 'val' [-Wunused-variable]
   96 |     ll cur = t[k].x, val = t[k].y;
      |                      ^~~

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