Submission #1044733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044733		Kel_Mahmut	Bridges (APIO19_bridges)	C++14	27 / 100	248 ms	11404 KiB

bridges

#include <bits/stdc++.h>
#define pb push_back
// #define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

struct DSU{
	int n;
	vector<int> par;
	vector<int> sz;
	DSU(int n) : n(n), par(n), sz(n, 1){
		for(int i = 0; i < n; i++) par[i] = i;
	}

	int find(int u){
		if(par[u] == u) return u;
		return par[u] = find(par[u]);
	}

	void merge(int u, int v){
		u = find(u);
		v = find(v);
		if(u == v) return;
		if(sz[v] > sz[u]) swap(u, v);
		par[v] = u;
		sz[u] += sz[v];
	}

	int cnt(int u){
		u = find(u);
		return sz[u];
	}
};

int main(){
	int n, m;
	cin >> n >> m;
	vector<vector<pair<int, int>>> g(n);
	vector<pair<pair<int, int>, pair<int, int>>> bri(m);
	vector<array<int, 3>> edge;
	for(int i = 0; i < m; i++){
		int u, v, c;
		cin >> u >> v >> c;
		u--, v--;
		g[u].pb(make_pair(v, c));
		g[v].pb(make_pair(u, c));
		bri[i] = make_pair(make_pair(u, g[u].size() - 1), make_pair(v, g[v].size() - 1));
		edge.pb({c, u, v});
	}
	int q; cin >> q;
	if(n <= 1000 && m <= 1000 && q <= 10000){
		int ans = 0;
		vector<int> vis(n);
		function<void(int, int)> dfs = [&](int u, int d){
			vis[u] = 1;
			ans++;
			for(auto [v, c]: g[u]){
				if(d <= c){
					if(!vis[v])
						dfs(v, d);
				}
			}
		};
		for(int i = 0; i < q; i++){
			int t;
			cin >> t;
			if(t == 2){
				int u, d;
				cin >> u >> d;
				u--;
				dfs(u, d);
				cout << ans << endl;
				ans = 0;
				vis.assign(n, 0);
			}
			else{
				int ind, c;
				cin >> ind >> c;
				ind--;
				auto x = bri[ind].first;
				g[x.first][x.second].second = c;
				x = bri[ind].second;
				g[x.first][x.second].second = c;
			}
		}
		exit(0);
	}

	sort(all(edge));
	reverse(all(edge));
	vector<array<int, 3>> Q;
	for(int i = 0; i < q; i++){
		int t;
		cin >> t;
		if(t == 2){
			int u, c;
			cin >> u >> c;
			u--;
			Q.pb({c, u, i});
		}
		else{
			int a, b;
			cin >> a >> b;
		}
	}

	sort(all(Q));
	reverse(all(Q));
	vector<int> ans(Q.size(), -1);
	DSU dsu(n);
	for(int i = 0, j = 0; j < (int) Q.size(); j++){
		while(i < m && edge[i][0] >= Q[j][0]){
			dsu.merge(edge[i][1], edge[i][2]);
			i++;
		}
		ans[Q[j][2]] = dsu.cnt(Q[j][1]);
	}

	for(int i = 0; i < (int) Q.size(); i++){
		cout << ans[i] << endl;
	}
}

Compilation message (stderr)

bridges.cpp: In lambda function:
bridges.cpp:58:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |    for(auto [v, c]: g[u]){
      |             ^

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