Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*#pragma GCC optimize("Ofast,no-stack-protector")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC optimize("fast-math")*/
- #include <iostream>
- #include <complex>
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <cstdio>
- #include <numeric>
- #include <cstring>
- #include <ctime>
- #include <cstdlib>
- #include <set>
- #include <map>
- #include <unordered_map>
- #include <unordered_set>
- #include <list>
- #include <cmath>
- #include <bitset>
- #include <cassert>
- #include <queue>
- #include <stack>
- #include <deque>
- #include <random>
- using namespace std;
- #define pb push_back
- #define all(x) x.begin(), x.end()
- #define rall(x) x.rbegin(), x.rend()
- #define Str(x) to_string(x)
- #define len(s) (int)s.size()
- typedef long long ll;
- typedef long double lld;
- typedef string str;
- typedef unsigned long long ull;
- const int maxn = 1e5 + 228;
- int dsu[maxn], sz[maxn];
- vector <int> t[maxn];
- map <int, bool> g[maxn];
- int get(int v) {
- return v == dsu[v] ? v : dsu[v] = get(dsu[v]);
- }
- void Merge(int a, int b) {
- a = get(a);
- b = get(b);
- if (a == b)
- return;
- if (sz[a] < sz[b])
- swap(a, b);
- sz[a] += sz[b];
- sz[b] = 0;
- for (auto it : g[b]) {
- int x = get(it.first);
- g[x][a] = true;
- g[a][x] = true;
- }
- dsu[b] = a;
- }
- void add(int a, int b) {
- a = get(a);
- b = get(b);
- if (a == b)
- assert(0);
- g[a][b] = 1;
- g[b][a] = 1;
- }
- void call(int a, int b) {
- a = get(a);
- b = get(b);
- if (a == b) {
- cout << "+\n";
- return;
- }
- if (g[a].count(b)) {
- cout << "-\n";
- } else {
- cout << "?\n";
- }
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- for (int i = 0; i < maxn; i++) {
- dsu[i] = i;
- sz[i] = 1;
- }
- int n, k;
- cin >> n >> k;
- for (int i = 0; i < k; i++) {
- char c;
- int x, y;
- cin >> c >> x >> y;
- if (c == '+') {
- Merge(x, y);
- } else if (c == '-'){
- add(x, y);
- } else {
- call(x, y);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement