Submission #733199

#	Time	Username	Problem	Language	Result	Execution time	Memory
733199		minhcool	Bridges (APIO19_bridges)	C++17	59 / 100	3043 ms	18324 KiB

bridges

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 1e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int n, m, q;

const int S = 305;

vector<pair<int, ii>> queries[N];

vector<iii> edges;

int answer[N];

int sz[N], rt[N];

int root(int x){
	return (x == rt[x] ? x : root(rt[x]));
}

stack<ii> stk;

int cnt = 0;

bool merge(int x, int y){
	x = root(x), y = root(y);
	if(x == y) return 0;
	if(sz[x] < sz[y]) swap(x, y);
	stk.push({x, sz[x]});
	stk.push({y, sz[y]});
	cnt += 2;
	sz[x] += sz[y];
	rt[y] = x;
	return 1;
}

int lst[N];

void process(){
	cin >> n >> m;
	edges.pb({{-1, -1}, -1});
	for(int i = 1; i <= m; i++){
		int x, y, w;
		cin >> x >> y >> w;
		edges.pb({{x, y}, -w});
	}
	cin >> q;
	for(int i = 1; i <= q; i++){
		int type, a, b;
		cin >> type >> a >> b;
		queries[i / S + 1].pb({type, {a, -b}});
	}
	set<ii> ok;
	for(int i = 1; i <= m; i++) ok.insert({edges[i].se, i});
	int cnt_que = 0;
	for(int i = 1; i <= 500; i++){
		if(!queries[i].size()) break;
		vector<iii> ask;
		int cnt2 = cnt_que;
		for(auto it : queries[i]){// erase the edges that are related to this block
			cnt_que++;
			if(it.fi == 1){
				ok.erase({edges[it.se.fi].se, it.se.fi});
				//edges[it.se.fi].se = it.se.fi;
			}
			else{
				// {weight, node, ind}
				ask.pb({{it.se.se, it.se.fi}, cnt_que});
			}
		}
		for(int j = 1; j <= n; j++){
			sz[j] = 1, rt[j] = j;
		}
		while(!stk.empty()) stk.pop();
		cnt = 0;
		sort(ask.begin(), ask.end());
		//for(auto it : ok) cout << "OK " << it.fi << " " << it.se << "\n";
		set<ii>::iterator it2 = ok.begin();
		for(auto it : ask){
		//	cout << "ASK " << it.fi.fi << " " << it.fi.se << " " << it.se << "\n";
			for(; it2 != ok.end(); it2++){
				if((*it2).fi > it.fi.fi) break;
				merge(edges[(*it2).se].fi.fi, edges[(*it2).se].fi.se);
			}
			cnt = 0;
			int cnt3 = cnt2;
			for(auto it2 : queries[i]) if(it2.fi == 1) lst[it2.se.fi] = edges[it2.se.fi].se;
			for(auto it2 : queries[i]){
				cnt3++;
				if(cnt3 == it.se) break;
				//if(it.fi == 2 && it.se)
				if(it2.fi == 1) lst[it2.se.fi] = it2.se.se;
			}
			for(auto it2 : queries[i]) if(it2.fi == 1 && lst[it2.se.fi] <= it.fi.fi) merge(edges[it2.se.fi].fi.fi, edges[it2.se.fi].fi.se);
			answer[it.se] = sz[root(it.fi.se)];
			for(int i = 1; i <= cnt; i++){
				assert(!stk.empty());
				int u = stk.top().fi, s = stk.top().se;
				rt[u] = u;
				sz[u] = s;
				stk.pop();
			}
		}
		// at the end of the block, update everything
		for(auto it : queries[i]) if(it.fi == 1) edges[it.se.fi].se = it.se.se;
		for(auto it : queries[i]) if(it.fi == 1) ok.insert({edges[it.se.fi].se, it.se.fi});
	}
	for(int i = 1; i <= q; i++) if(answer[i]) cout << answer[i] << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}

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