Submission #447521

#	Time	Username	Problem	Language	Result	Execution time	Memory
447521		S2speed	Bridges (APIO19_bridges)	C++17	43 / 100	121 ms	20400 KiB

bridges

#include<bits/stdc++.h>

using namespace std;

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;
typedef pair<bool , pll> plll;

const ll maxn = 3e5 + 16 , inf = 2e18;

ll n , m , q;
ll v[maxn] , u[maxn] , w[maxn];
vector<ll> adj[maxn];
bitset<maxn> mark;
ll cnt;

void DFS(ll r){
	mark[r] = true;
	cnt++;
	for(auto i : adj[r]){
		if(mark[i]) continue;
		DFS(i);
	}
	return;
}

void sub1(){
	for(ll e = 0 ; e < q ; e++){
		ll t;
		cin>>t; t--;
		if(t){
			cnt = 0;
			for(ll i = 0 ; i < n ; i++){
				mark[i] = false;
				adj[i].clear();
			}
			ll s , r;
			cin>>s>>r; s--;
			for(ll i = 0 ; i < m ; i++){
				if(w[i] >= r){
					adj[v[i]].push_back(u[i]); adj[u[i]].push_back(v[i]);
				}
			}
			DFS(s);
			cout<<cnt<<'\n';
		} else {
			ll b , r;
			cin>>b>>r; b--;
			w[b] = r;
		}
	}
	return;
}

struct segtree {

	ll sz = 1;
	vector<ll> val;

	void init(ll n){
		while(sz < n) sz <<= 1;
		val.assign(sz << 1 , inf);
		return;
	}

	void set(ll i , ll k , ll x , ll lx , ll rx){
		if(rx - lx == 1){
			val[x] = k;
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		if(i < m){
			set(i , k , ln , lx , m);
		} else {
			set(i , k , rn , m , rx);
		}
		val[x] = min(val[ln] , val[rn]);
		return;
	}

	void set(ll i , ll k){
		set(i , k , 0 , 0 , sz);
		return;
	}

	ll cal(ll i , ll k , bool c , ll x , ll lx , ll rx){
		if(c){
			if(rx <= i) return inf;
			if(val[x] >= k) return inf;
			if(rx - lx == 1) return lx;
			ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
			ll a = cal(i , k , c , ln , lx , m);
			if(a != inf) return a;
			a = cal(i , k , c , rn , m , rx);
			return a;
		} else {
			if(lx >= i) return -1;
			if(val[x] >= k) return -1;
			if(rx - lx == 1) return lx;
			ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
			ll a = cal(i , k , c , rn , m , rx);
			if(a != -1) return a;
			a = cal(i , k , c , ln , lx , m);
			return a;
		}
	}

	ll cal(ll i , ll k , bool c){
		return cal(i , k , c , 0 , 0 , sz);
	}

};

segtree st;

void sub2(){
	st.init(n - 1);
	for(ll i = 0 ; i < n - 1 ; i++){
		st.set(i , w[i]);
	}
	for(ll e = 0 ; e < q ; e++){
		ll t;
		cin>>t; t--;
		if(t){
			ll s , y , l , r;
			cin>>s>>y; s--;
			l = st.cal(s , y , 0);
			r = min(n - 1 , st.cal(s , y , 1));
			cout<<r - l<<'\n';
		} else {
			ll b , r;
			cin>>b>>r; b--;
			st.set(b , r);
		}
	}
	return;
}

ll ds[maxn] , dsz[maxn];

ll dsu(ll v){
	return (ds[v] == v ? v : ds[v] = dsu(ds[v]));
}

void merge(ll v , ll u){
	v = dsu(v); u = dsu(u);
	if(v == u) return;
	ds[u] = v;
	dsz[v] += dsz[u];
	return;
}

vector<pll> ed , qu;
ll ans[maxn] , s[maxn] , r[maxn];

void sub4(){
	for(ll i = 0 ; i < q ; i++){
		ll t;
		cin>>t>>s[i]>>r[i]; s[i]--;
		qu.push_back({r[i] , i});
		if(t == 1) return;
	}
	for(ll i = 0 ; i < m ; i++){
		ed.push_back({w[i] , i});
	}
	iota(ds , ds + n , 0);
	fill(dsz , dsz + n , 1);
	sort(all(qu) , greater<pll>()); qu.push_back({-1 , -1});
	sort(all(ed) , greater<pll>());
	ll x = 0;
	for(ll i = 0 ; i < m ; i++){
		while(qu[x].first > ed[i].first){
			ll j = qu[x++].second;
			ans[j] = dsz[dsu(s[j])];
		}
		ll j = ed[i].second;
		merge(v[j] , u[j]);
	}
	while(x < q){
		ll j = qu[x++].second;
		ans[j] = dsz[dsu(s[j])];
	}
	for(ll i = 0 ; i < q ; i++){
		cout<<ans[i]<<'\n';
	}
	return;
}

int main(){
	ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);

	cin>>n>>m;
	for(ll i = 0 ; i < m ; i++){
		cin>>v[i]>>u[i]>>w[i]; v[i]--; u[i]--;
	}
	cin>>q;
	if(n <= 1e3 && m <= 1e3 && q <= 1e4){
		sub1();
		return 0;
	}
	bool ch = true;
	for(ll i = 0 ; i < m ; i++){
		ch &= (v[i] == i);
		ch &= (u[i] == i + 1);
	}
	if(ch){
		sub2();
		return 0;
	}
	sub4();
	return 0;
}

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