Submission #1044684

#TimeUsernameProblemLanguageResultExecution timeMemory
1044684Kel_MahmutBridges (APIO19_bridges)C++14
0 / 100
105 ms5560 KiB
#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<array<int, 3>> edge(m);
	for(int i = 0; i < m; i++){
		int u, v, c;
		cin >> u >> v >> c;
		u--, v--;
		edge.pb({c, u, v});
	}

	sort(all(edge));

	int q;
	cin >> q;
	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));
	vector<int> ans(Q.size());
	DSU dsu(n);
	for(int i = 0, j = 0; j < (int) Q.size() && i < m; 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;
	}
}

#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...