fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define Long long long
  6. #define bint __int128
  7. #define _3bkarm cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
  8.  
  9. const int mod = 998244353;
  10.  
  11. vector<int> p, root;
  12. vector<int> treeSize;
  13. vector< set<int> > adj;
  14.  
  15. int update;
  16. void dfs(int v) {
  17.     root[v] = update;
  18.     for (int u : adj[v]) {
  19.         if (u == p[v]) continue;
  20.         p[u] = v, dfs(u);
  21.     }
  22. }
  23.  
  24. void get_shit_done() {
  25.     int n, q;
  26.     cin >> n >> q;
  27.  
  28.     p.assign(n + 1, -1);
  29.     treeSize.assign(n + 1, 1);
  30.     adj.assign(n + 1, {});
  31.     root.assign(n + 1, -1);
  32.     for (int v = 1; v <= n; ++v) root[v] = v;
  33.  
  34.     int x = 0;
  35.     while (q--) {
  36.         int a, b, c;
  37.         cin >> a >> b >> c;
  38.  
  39.         a = 1 + (1LL * a * (1 + x) % mod) % 2;
  40.         b = 1 + (1LL * b * (1 + x) % mod) % n;
  41.         c = 1 + (1LL * c * (1 + x) % mod) % n;
  42.  
  43.         if (a == 1) {
  44.             if ( treeSize[ root[b] ] < treeSize[ root[c] ] )
  45.                 swap(b, c);
  46.             treeSize[ root[b] ] += treeSize[ root[c] ];
  47.             p[c] = b;
  48.             adj[b].insert(c);
  49.             adj[c].insert(b);
  50.             update = root[b], dfs(c);
  51.         } else {
  52.             if (p[b] == p[c] and p[b] != -1) x = p[b];
  53.             else if ( adj[b].count(p[c]) ) x = p[c];
  54.             else if ( adj[c].count(p[b]) ) x = p[b];
  55.             else x = 0;
  56.             cout << x << '\n';
  57.         }
  58.     }
  59. }
  60.  
  61. signed main() {
  62.     _3bkarm
  63.  
  64.     int ts = 1;
  65. //    cin >> ts;
  66.     while (ts--) {
  67.         get_shit_done();
  68.     }
  69.  
  70.     return 0;
  71. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/XLotsM
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

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!