fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define int long long
  5. const int N = 1e5 + 5, mod = 998244353;
  6. set<set<int>> edges;
  7. int par[N];
  8. vector<int> adj[N];
  9.  
  10. struct DSU {
  11.   vector<int> par, sz;
  12.  
  13.   DSU() {
  14.     sz.assign(N, 1);
  15.     par.resize(N);
  16.     iota(par.begin(), par.end(), 0);
  17.   }
  18.  
  19.   int F(int x) { return par[x] == x ? x : (par[x] = F(par[x])); }
  20.  
  21.   void mrg(int u, int v) {
  22.     u = F(u), v = F(v);
  23.     sz[v] += sz[u];
  24.     par[u] = v;
  25.   }
  26.  
  27.   bool check(int u, int v) {
  28.     int f = sz[F(u)], s = sz[F(v)];
  29.     return f > s;
  30.   }
  31. } dsu;
  32.  
  33. void mrg(int u, int v) {
  34.   if (!par[u]) {
  35.     par[u] = v;
  36.   } else if (!par[v]) {
  37.     par[v] = u;
  38.   } else {
  39.     if (dsu.check(u, v)) swap(u, v);
  40.     queue<pair<int, int>> q;
  41.     q.push({u, u});
  42.     par[u] = v;
  43.     while (q.size()) {
  44.       auto [nd, p] = q.front();
  45.       q.pop();
  46.       for (int &x: adj[nd]) {
  47.         if (x == p)continue;
  48.         par[x] = nd;
  49.         q.push({x, nd});
  50.       }
  51.     }
  52.   }
  53.   dsu.mrg(u, v);
  54.   adj[u].emplace_back(v);
  55.   adj[v].emplace_back(u);
  56.   edges.insert({u, v});
  57. }
  58.  
  59. int32_t main() {
  60.   ios_base::sync_with_stdio(false);
  61.   cin.tie(nullptr);
  62.   iota(par, par + N, 0);
  63.   int n, q;
  64.   cin >> n >> q;
  65.   int l = 1;
  66.   for (int i = 0; i < q; ++i) {
  67.     int a, b, c;
  68.     cin >> a >> b >> c;
  69.     int t = 1 + (a * l % mod % 2);
  70.     int u = 1 + (b * l % mod % n);
  71.     int v = 1 + (c * l % mod % n);
  72.     if (t == 1) {
  73.       mrg(u, v);
  74.     } else {
  75.       int pu = par[u], pv = par[v];
  76.       int ans = 0;
  77.       if (pu == pv && pv) {
  78.         ans = pu;
  79.       } else if (pu && edges.count({pu, v})) {
  80.         ans = pu;
  81.       } else if (pv && edges.count({pv, u})) {
  82.         ans = pv;
  83.       }
  84.       cout << ans << '\n';
  85.       l = ans + 1;
  86.     }
  87.  
  88.   }
  89. }
Runtime error #stdin #stdout 0.04s 7984KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0A7I3e
language:
C++14 (clang 8.0)
created:
216 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!