Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <list>
- #include <algorithm>
- #include <string>
- #include <math.h>
- #include <climits>
- #include <stack>
- //#include <chrono>
- //#include <fstream>
- //#include <bits/stdc++.h>
- #define mp make_pair
- #define pb push_back
- #define eb emplace_back
- #define x first
- #define y second
- #define sz(x) (int)x.size()
- #define all(x) begin(x), end(x)
- #define rall(x) rbegin(x), rend(x)
- #define FOR(i,a,b) for (int i = (a); i < (b); i++)
- #define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- typedef long double ld;
- typedef pair<int, int> pi;
- typedef pair<ll, ll> pl;
- typedef vector<int> veci;
- typedef vector<bool> vecb;
- typedef vector<vector<int>> vvi;
- typedef vector<vector<bool>> vvb;
- const int INF_I = 1e9;
- const ll INF_LL = 1e18;
- class DSU {
- public:
- DSU(int n) {
- this->n = n;
- p.assign(n, 0);
- sz.assign(n, 0);
- for (int i = 0; i < n; i++)
- p[i] = i;
- }
- void union_sets(int a, int b) {
- a = find_set(a);
- b = find_set(b);
- if (a != b) {
- if (sz[a] < sz[b])
- swap(a, b);
- p[b] = a;
- sz[a] += sz[b];
- }
- }
- bool get(int a, int b) {
- return find_set(a) == find_set(b);
- }
- private:
- int n;
- veci p;
- veci sz;
- int find_set(int v) {
- return (v == p[v] ? v : p[v] = find_set(p[v]));
- }
- };
- int main() {
- /*ifstream cin("in.txt");
- ofstream cout("out.txt");
- auto start_time = chrono::high_resolution_clock::now();*/
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int n, m, k;
- cin >> n >> m >> k;
- for (int i = 0; i < m; i++) {
- int a;
- cin >> a >> a;
- }
- stack<pair<bool, pi>> q;
- for (int i = 0; i < k; i++) {
- string str; int a, b;
- cin >> str >> a >> b;
- --a, --b;
- if (str[0] == 'a')
- q.emplace(mp(0, mp(a, b)));
- else
- q.emplace(mp(1, mp(a, b)));
- }
- DSU d(n);
- stack<bool> res;
- while (!q.empty()) {
- pair<int, pi> p = q.top();
- q.pop();
- if (p.x)
- d.union_sets(p.y.x, p.y.y);
- else
- res.emplace(d.get(p.y.x, p.y.y));
- }
- while (!res.empty()) {
- cout << (res.top() ? "YES" : "NO") << "\n";
- res.pop();
- }
- /*auto end_time = chrono::high_resolution_clock::now();
- chrono::duration<double> duration = end_time - start_time;
- cout << duration.count() << "\n";
- cin.close();
- cout.close();*/
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment