Submission #402567

#	Time	Username	Problem	Language	Result	Execution time	Memory
402567		cstuart	Bridges (APIO19_bridges)	C++17	73 / 100	3063 ms	15736 KiB

bridges

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

typedef int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef tuple<ll, ll, ll> tl;
typedef tuple<ll, ll, ll, ll> ql;

const ll INF = 1000000000000000000ll;
const ll MOD = 1000000007ll;
const ll BUCKET_SIZE = 800;

ll N, M, U[100005], V[100005], D[100005], Q, T[100005], X[100005], Y[100005];
ll head[100005], card[100005], ans[100005];
bool is_stable[100005], vis_arr[100005];
vector <ll> dynamic_edgelist;
vector <pl> dynamic_limit[100005];
vector <tl> operations;                // (value, type, index), type 0 -> stable edge, type 1 -> query
vector <ll> dynamic_adj[100005];
vector <ll> vis_vec;
queue <ll> bfs_proc;

ll get_head(ll x) {
	if (head[x] == x) return x;
	else return head[x] = get_head(head[x]);
}

int main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> M;
	
	for (ll i = 1; i <= M; i++) {
		cin >> U[i] >> V[i] >> D[i];
	}
	
	cin >> Q;
	
	for (ll q = 1; q <= Q; q++) {
		cin >> T[q] >> X[q] >> Y[q];
	}
	
	for (ll i = 1; i <= N; i++) {
		head[i] = i;
		card[i] = 1;
	}
	
	for (ll i = 1; i <= M; i++) {
		is_stable[i] = 1;
	}
	
	for (ll b = 1; (b - 1) * BUCKET_SIZE + 1 <= Q; b++) {
		
		// separate into stable and dynamic edges, fill operations
		
		for (ll q = (b - 1) * BUCKET_SIZE + 1; q <= min(b * BUCKET_SIZE, Q); q++) {
			if (T[q] == 1) {
				if (is_stable[X[q]]) {
					is_stable[X[q]] = 0;
					dynamic_limit[X[q]].emplace_back(-1, D[X[q]]);
				}
				dynamic_limit[X[q]].emplace_back(q, Y[q]);
			} else {
				operations.emplace_back(Y[q], 0, q);
			}
		}
		
		for (ll i = 1; i <= M; i++) {
			if (is_stable[i]) {
				operations.emplace_back(D[i], 1, i);
			} else {
				dynamic_edgelist.push_back(i);
			}
		}
		
		sort(operations.begin(), operations.end(), greater<tl>());
		
		// cout << "part 1 ok\n";
		
		// offline edge adding and query handling
		
		for (tl op : operations) {
			
			ll type = get<1>(op);
			
			if (type == 1) {
				
				ll stable_edge_index = get<2>(op);
				
				// cout << "merging edge " << stable_edge_index << "\n";
				
				ll hu = get_head(U[stable_edge_index]);
				ll hv = get_head(V[stable_edge_index]);
				
				if (hu != hv) {
					if (card[hu] < card[hv]) swap(hu, hv);
					card[hu] += card[hv];
					head[hv] = hu;
				}
				
			} else {
				
				ll query_index = get<2>(op);
				
				// cout << "handling query " << query_index << "\n";
				
				ll start_node_index = get_head(X[query_index]);
				ans[query_index] = 0;
				bfs_proc.push(start_node_index);
				vis_arr[start_node_index] = 1;
				vis_vec.push_back(start_node_index);
				
				for (ll dynamic_edge_index : dynamic_edgelist) {
					auto it = upper_bound(dynamic_limit[dynamic_edge_index].begin(),
					                      dynamic_limit[dynamic_edge_index].end(),
										  make_pair(query_index, INF));
					ll u = get_head(U[dynamic_edge_index]);
					ll v = get_head(V[dynamic_edge_index]);
					ll d = (*prev(it)).second;
					if (d < Y[query_index]) continue;
					dynamic_adj[u].push_back(v);
					dynamic_adj[v].push_back(u);
				}
				
				// cout << "  init ok\n";
				
				while (!bfs_proc.empty()) {
					ll cur_n = bfs_proc.front();
					bfs_proc.pop();
					ans[query_index] += card[cur_n];
					for (ll nex_n : dynamic_adj[cur_n]) {
						if (!vis_arr[nex_n]) {
							vis_arr[nex_n] = 1;
							vis_vec.push_back(nex_n);
							bfs_proc.push(nex_n);
						}
					}
				}
				
				// cout << "  bfs ok\n";
				
				for (ll vis_index : vis_vec) {
					vis_arr[vis_index] = 0;
				}
				
				vis_vec.clear();
				
				for (ll dynamic_edge_index : dynamic_edgelist) {
					dynamic_adj[get_head(U[dynamic_edge_index])].clear();
					dynamic_adj[get_head(V[dynamic_edge_index])].clear();
				}
				
				// cout << "  reset ok\n";
				
				// cout << "  answer " << ans[query_index] << "\n";
				
			}
			
		}
		
		// cout << "part 2 ok\n";
		
		// reset
		
		for (ll i : dynamic_edgelist) {
			D[i] = dynamic_limit[i].back().second;
			dynamic_limit[i].clear();
		}
		
		for (ll i = 1; i <= N; i++) {
			head[i] = i;
			card[i] = 1;
		}
		
		for (ll i = 1; i <= M; i++) {
			is_stable[i] = 1;
		}
		
		dynamic_edgelist.clear();
		operations.clear();
		
		// cout << "part 3 ok\n";
		
	}
	
	for (ll q = 1; q <= Q; q++) {
		if (T[q] == 2) cout << ans[q] << "\n";
	}
	
	return 0;
}

Compilation message (stderr)

bridges.cpp:10:16: warning: overflow in conversion from 'long long int' to 'll' {aka 'int'} changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
   10 | const ll INF = 1000000000000000000ll;
      |                ^~~~~~~~~~~~~~~~~~~~~

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