Submission #73704948

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int kMod = 998'244'353;

struct DisjointSet {
    vector<int> parent;
    vector<int> sz;
    int curr;

    DisjointSet(int n) {
        parent.assign(n, 0);
        sz.assign(n, 1);

        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
        curr = n - 1;
    }

    int find(int x) {
        if (x != parent[x]) {
            parent[x] = find(parent[x]);
        }

        return parent[x];
    }

    void unite(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) {
            return;
        }

        if (sz[a] > sz[b]) {
            swap(a, b);
        }

        parent[a] = b;
        sz[b] += sz[a];
    }
};

int power(int a, int b) {
    int res = 1;

    while (b) {
        if (b & 1) {
            res = (res * a) % kMod;
        }

        a = (a * a) % kMod;
        b >>= 1;
    }

    return res;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    int base = 0;
    int res = 0;
    int cnt = 0;
    DisjointSet ds(N + 1);
    vector<pair<int, int>> edges(M + 1);

    for (int i = 1; i <= M; ++i) {
        cin >> edges[i].first >> edges[i].second;
    }

    for (int i = M; i >= 1; --i) {
        auto [u, v] = edges[i];
        if (ds.find(u) != ds.find(v)) {
            if (ds.curr > 2) {
                ds.unite(u, v);
                --ds.curr;
            }

            else {
                res = (res + power(2, i)) % kMod;
            }
        }
        
    }

    cout << res;
}

Submission Info

Compile Error

./Main.cpp: In function 'int main()':
./Main.cpp:69:9: warning: unused variable 'base' [-Wunused-variable]
   69 |     int base = 0;
      |         ^~~~
./Main.cpp:71:9: warning: unused variable 'cnt' [-Wunused-variable]
   71 |     int cnt = 0;
      |         ^~~

Judge Result