提出 #54770729

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using pl = pair<ll, ll>;
constexpr ll INF = 1e9 + 7;
constexpr ll mod = 998244353;
constexpr ld eps = 1e-9;
const ld PI = acos(-1);

vector<int> pred, cnt;

int find(int x) {
    return x == pred[x] ? x : find(pred[x]);
}

void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y)return;
    if (cnt[x] > cnt[y])swap(x, y);
    cnt[y] += cnt[x];
    pred[x] = y;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    pred.resize(n);
    iota(pred.begin(), pred.end(), 0);
    cnt.resize(n, 1);
    vector<vector<int>> g(n);
    vector<int> d(n, 0);
    vector<int> pr(n, -1);
    auto dfs = [&](auto &&dfs, int v, int p) -> void {
        for (auto to: g[v]) {
            if (to == p)continue;
            d[to] = d[v] + 1;
            pr[to] = v;
            dfs(dfs, to, v);
        }
    };
    auto solve = [&](int x, int y) {
        if (find(x) != find(y))return -1;
        if (d[x] < d[y])swap(x, y);
        x = pr[x];
        if (pr[x] == y || pr[y] == x)return x;
        return -1;
    };
    ll ans{0};
    while (q--) {
        ll a, b, c;
        cin >> a >> b >> c;
        ll t = (((a * (1 + ans)) % mod) % 2);
        ll u = (((b * (1 + ans)) % mod) % n);
        ll v = (((c * (1 + ans)) % mod) % n);
        if (!t) {
            if (cnt[find(u)] > cnt[find(v)]) {
                swap(u, v);
            }
            pr[u] = v;
            d[u] = d[v] + 1;
            dfs(dfs, u, v);
            unite(u, v);
            g[u].push_back(v);
            g[v].push_back(u);
        } else {
            ans = solve(u, v) + 1;
            cout << ans << "\n";
        }
    }
    return 0;
}

提出情報

ジャッジ結果