제출 #1044700

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1044700		Kel_Mahmut	다리 (APIO19_bridges)	C++14	14 / 100	123 ms	5872 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<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));
	reverse(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));
	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;
	}
}

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