Submission #2543168

---

Source Code Expand

#include "iostream"
#include "algorithm"
#include "string"
#include "set"
#include "vector"
#include "queue"
#include "iomanip"
#include "map"

using namespace std;

const long long int MOD = 1000000007;

long long int N, M, K, H, W;

class UnionFind {
	vector<int>parent;
	vector<int>rank;
	vector<int>si;
public:
	UnionFind(int num) {
		num++;
		parent.resize(num);
		rank.resize(num);
		si.resize(num);
		for (int i = 0; i < num; i++) {
			parent[i] = i;
			rank[i] = 0;
			si[i] = 1;
		}
	}
	int Find(int node) {
		if (parent[node] == node)return node;
		else return parent[node] = Find(parent[node]);
	}
	void Unite(int u, int v) {
		u = Find(u);
		v = Find(v);
		if (u == v)return;
		if (rank[u] < rank[v]) {
			parent[u] = v;
			si[v] += si[u];
		}
		else {
			parent[v] = u;
			si[u] += si[v];
			if (rank[u] == rank[v])rank[u]++;
		}
	}
	bool Check_Same(int u, int v) {
		return Find(u) == Find(v);
	}
	int Get_Size(int node) {
		return si[Find(node)];
	}
};

struct Query {
	bool connect;
	int l;
	int r;
	int st;
	int year;
	int index;
	Query(){
		connect = false;
	}
	bool operator <(const Query& q)const {
		return year < q.year;
	}
	bool operator >(const Query& q)const {
		return year > q.year;
	}
};

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> M;
	vector<Query>v;
	for (int i = 0; i < M; i++) {
		Query q;
		cin >> q.l >> q.r >> q.year;
		q.year *= 2;
		q.connect = true;
		v.push_back(q);
	}
	cin >> K;
	for (int i = 0; i < K; i++) {
		Query q;
		cin >> q.st >> q.year;
		q.year *= 2;
		q.year++;
		q.index = i;
		v.push_back(q);
	}
	vector<int>ans(K);
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	UnionFind uf(N);
	for (auto i : v) {
		if (i.connect) {
			uf.Unite(i.l, i.r);
		}
		else {
			ans[i.index] = uf.Get_Size(i.st);
		}
	}
	for (auto i : ans) {
		cout << i << endl;
	}
	return 0;
}

Submission Info

Judge Result