Submission #491130

#TimeUsernameProblemLanguageResultExecution timeMemory
491130S2speedBridges (APIO19_bridges)C++17
0 / 100
93 ms34044 KiB
#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cerr<<"--------------------------------------"<<endl
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<ll , pll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;

const ll maxn = 1e5 + 16 , md = 1e9 + 7 , inf = 2e16;

ll gcd(ll a , ll b){
	if(a < b) swap(a , b);
	if(b == 0) return a;
	return gcd(b , a % b);
}

inline ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n; res %= md;
		}
		n *= n; n %= md;
		k >>= 1;
	}
	return res;
}

ll ds[maxn] , dsz[maxn];
vector<ll> dv;

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

void merge(ll v , ll u){
	v = dsu(v); u = dsu(u);
	if(v == u){
		dv.push_back(-1);
		return;
	}
	if(dsz[v] < dsz[u]) swap(v , u);
	ds[u] = v;
	dsz[v] += dsz[u];
	dv.push_back(u);
	return;
}

void undo(){
	if(dv.back() == -1){
		dv.pop_back();
		return;
	}
	ll u = dv.back();
	dsz[ds[u]] -= dsz[u];
	ds[u] = u;
	dv.pop_back();
	return;
}

vector<pll> ed , upd[maxn] , qn , wn;
ll w[maxn];
bitset<maxn> mark;
vector<plll> t;
vector<ll> en;
ll ans[maxn];

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

	ll n , m;
	cin>>n>>m;
	for(ll i = 0 ; i < m ; i++){
		ll v , u;
		cin>>v>>u>>w[i]; v--; u--;
		ed.push_back({v , u});
		upd[i].push_back({-1 , w[i]});
	} ed.push_back({0 , 0});
	ll q;
	cin>>q;
	for(ll i = 0 ; i < q ; i++){
		ll y , v , k;
		cin>>y>>v>>k; v--;
		t.push_back({y , {v , k}});
		if(y == 1){
			upd[v].push_back({i , k});
		}
	}
	wall;
	ll sq = min(q , 340ll);
	for(ll e = 0 ; e < q ; e += sq){
		mark.reset();
		en.clear();
		qn.clear();
		iota(ds , ds + n , 0);
		fill(dsz , dsz + n , 1);
		dv.clear();
		for(ll i = e ; i < e + sq ; i++){
			if(t[i].first == 1){
				mark[t[i].second.first] = true;
			} else {
				qn.push_back({t[i].second.second , i});
			}
		}
		for(ll i = 0 ; i < m ; i++){
			if(mark[i]){
				en.push_back(i);
				w[i] = upd[i][lower_bound(all(upd[i]) , mp(e + sq , -1ll)) - upd[i].begin() - 1].second;
			} else {
				wn.push_back({w[i] , i});
			}
		}
		sort(all(wn) , greater<pll>()); wn.push_back({-1 , m});
		sort(all(en));
		sort(all(qn) , greater<pll>()); qn.push_back({-1 , -1});
		ll x = 0;
		for(auto p : wn){
			while(true){
				ll k = qn[x].first , r = qn[x].second , cnt = 0;
				if(k <= p.first) break;
				for(auto j : en){
					ll u = upd[j][lower_bound(all(upd[j]) , mp(r , -1ll)) - upd[j].begin() - 1].second;
					if(u >= k){
						merge(ed[j].first , ed[j].second);
						cnt++;
					}
				}
				ans[r] = dsz[dsu(t[r].second.second)];
				while(cnt){
					undo(); cnt--;
				}
				x++;
			}
			ll j = p.second;
			merge(ed[j].first , ed[j].second);
		}
	}
	for(ll i = 0 ; i < q ; i++){
		if(t[i].first == 1) continue;
		cout<<ans[i]<<'\n';
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...