Submission #491179

#	Time	Username	Problem	Language	Result	Execution time	Memory
491179		S2speed	Bridges (APIO19_bridges)	C++17	100 / 100	2761 ms	15176 KiB

bridges

#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;
}

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

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

void merge(int v , int 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;
	}
	int u = dv.back();
	dsz[ds[u]] -= dsz[u];
	ds[u] = u;
	dv.pop_back();
	return;
}

vector<pii> ed , upd[maxn] , qn , wn;
int w[maxn];
bitset<maxn> mark;
vector<piii> t;
vector<int> en;
int ans[maxn];

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

	int n , m;
	cin>>n>>m;
	for(int i = 0 ; i < m ; i++){
		int 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});
	int q;
	cin>>q;
	for(int i = 0 ; i < q ; i++){
		int y , v , k;
		cin>>y>>v>>k; v--;
		t.push_back({y , {v , k}});
		if(y == 1){
			upd[v].push_back({i , k});
		}
	}
	int sq = min(q , 600);
	for(int e = 0 ; e < q ; e += sq){
		mark.reset();
		en.clear();
		wn.clear();
		qn.clear();
		iota(ds , ds + n , 0);
		fill(dsz , dsz + n , 1);
		dv.clear();
		for(int i = e ; i < min(e + sq , q) ; i++){
			if(t[i].first == 1){
				mark[t[i].second.first] = true;
			} else {
				qn.push_back({t[i].second.second , i});
			}
		}
		for(int i = 0 ; i < m ; i++){
			if(mark[i]){
				en.push_back(i);
				w[i] = upd[i][lower_bound(all(upd[i]) , mp(e + sq , -1)) - upd[i].begin() - 1].second;
			} else {
				wn.push_back({w[i] , i});
			}
		}
		sort(all(wn) , greater<pii>()); wn.push_back({-1 , m});
		sort(all(en));
		sort(all(qn) , greater<pii>()); qn.push_back({-1 , -1});
		int x = 0;
		for(auto p : wn){
			while(true){
				int k = qn[x].first , r = qn[x].second , cnt = 0;
				if(k <= p.first) break;
				for(auto j : en){
					int u = upd[j][lower_bound(all(upd[j]) , mp(r , -1)) - upd[j].begin() - 1].second;
					if(u >= k){
						merge(ed[j].first , ed[j].second);
						cnt++;
					}
				}
				ans[r] = dsz[dsu(t[r].second.first)];
				while(cnt){
					undo(); cnt--;
				}
				x++;
			}
			int j = p.second;
			merge(ed[j].first , ed[j].second);
		}
	}
	for(int i = 0 ; i < q ; i++){
		if(t[i].first == 1) continue;
		cout<<ans[i]<<'\n';
	}
	return 0;
}

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