結果

問題 No.1451 集団登校
ユーザー souma987souma987
提出日時 2021-03-31 15:55:07
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 5,947 bytes
コンパイル時間 4,646 ms
コンパイル使用メモリ 237,796 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-05-08 19:08:55
合計ジャッジ時間 8,688 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 36 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 RE -
testcase_11 AC 11 ms
5,376 KB
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 AC 8 ms
5,376 KB
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

// Created at 2021/03/31 14:00
// {TODO}WA, {TODO}min, {TODO}diff
// goal: {TODO}min
#include <bits/stdc++.h>
#include <atcoder/all>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define overload4(_1,_2,_3,_4,name,...) name
#define rep(i, n) for (lint i = 0, i##_lim = n; i < i##_lim; i++)
#define rep2(i, n) for (lint i = 1, i##_lim = n; i <= i##_lim; i++)
#define rep3(i, s, e) for (lint i = s, i##_lim = e; i < i##_lim; i++)
#define all(i) (i).begin(), (i).end()
#define print1(s) cout << (s) << '\n';
#define print2(s1, s2) cout << (s1) << ' ' << (s2) << '\n';
#define print3(s1, s2, s3) cout << (s1) << ' ' << (s2) << ' ' << (s3) << '\n';
#define print4(s1, s2, s3, s4) cout << (s1) << ' ' << (s2) << ' ' << (s3) << ' ' << (s4) << '\n';
#define print(...) overload4(__VA_ARGS__, print4, print3, print2, print1)(__VA_ARGS__)
using namespace std;
using namespace atcoder;
using lint = long long;
using ld = long double;
using pi = pair<int, int>;
using pl = pair<lint, lint>;
using vi = vector<int>;
using vl = vector<lint>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using qi = queue<int>;
using ql = queue<lint>;
using qpi = queue<pi>;
constexpr int INF = 1 << 30;
constexpr lint INFl = 1LL << 62;

template<class T, class U>
istream &operator>>(istream &is, pair<T, U> &pair) {
    is >> pair.first >> pair.second;
    return is;
}

template<class T, class U>
ostream &operator<<(ostream &os, pair <T, U> &pair) {
    os << pair.first << ' ' << pair.second;
    return os;
}

template<class T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (auto &v : vec) is >> v;
    return is;
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
    os << '[';
    for (auto v : vec) os << v << ", ";
    os << ']';
    return os;
}

template<class T>
inline bool chmax(T &a, T b) {
    if (b > a) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

struct UnionFind {
    vi data;
    vi siz;
    vi cnt;
//    vi es;
//    int cnt;

    explicit UnionFind(int n) : data(n) , siz(n, 1) , cnt(n, 0)/* , es(n, 0) , cnt(n) */ {
        rep(i, n) data.at(i) = i;
    }

    int root(int x) {
        if (data.at(x) == x) return x;
        else {
            if (data.at(x) < 0) {
                int rtn = root(-data.at(x));
                if (rtn < 0) return data.at(x) = rtn;
                else {
                    return data.at(x) = -rtn - 1;
                }
            }
            else return data.at(x) = root(data.at(x));
        }
    }

    bool same(int x, int y) {
        return root(x) == root(y);
    }

    bool unite(int x, int y) {
        x = root(x);
        y = root(y);

        if (x < 0) x = -x - 1;
        if (y < 0) x = -y - 1;

        if (x == y) {
//            es.at(x)++;
            return false;
        }

        // union-by-size
        if (data.at(x) > data.at(y)) swap(x, y);

        if (siz.at(x) == siz.at(y)) {
            data.at(y) = x;
            cnt.at(x)++;
        }
        else data.at(y) = -x - 1;
        siz.at(x) += siz.at(y);
//        data.at(x) += data.at(y);

//        es.at(x) += es.at(y);
//        es.at(x)++;
//        cnt--;
        return true;
    }

    bool check(int x) {
        if (data.at(x) == x) return true;
        if (data.at(x) < 0) return false;
        return check(data.at(x));
    }

//    int size() const {
//        return cnt;
//    }
};

// @return ax + by = gcd(a, b) のとき、{gcd, x, y}
template<class T>
inline tuple<T, T, T> ext_gcd(T a, T b) {
    T x = 1, y = 0, u = 0, v = 1;
    while (b != 0) {
        T k = a / b;
        x -= k * u;
        y -= k * v;
        swap(x, u);
        swap(y, v);
        T r = a % b;
        a = b;
        b = r;
    }
    return make_tuple(a, x, y);
}

// @return 存在しない場合は -1
template<class T>
inline T mod_inv(T a, T mod) {
    T check, x, y;
    tie(check, x, y) = ext_gcd(a, mod);
    if (check == 1) {
        x %= mod;
        x += mod;
        x %= mod;
        return x;
    }
    else return -1;
}

// x = a / b (mod mod) のとき
// @return x = y (mod m) となるような y, m の pair
// 存在しない場合は(-1, -1)
template<class T>
inline pair<T, T> mod_div(T a, T b, T mod) {
    T divisor = __gcd(b, mod);
    if (a % divisor != 0) return make_pair(-1, -1);
    else {
        a /= divisor;
        b /= divisor;
        mod /= divisor;
        T inv = mod_inv(b, mod);
        return make_pair((a * inv % mod + mod) % mod, mod);
    }
}

constexpr lint MOD = 1000000007;

inline lint fast_pow(lint base, lint ex) {
    lint rtn = 1;
    // 繰り返し二乗法
    // log2(ex) 回繰り返す
    while (ex) {
        // 指数が奇数なら1回多くかけておく
        if (ex & 1) {
            rtn *= base;
            rtn %= MOD;
        }
        base *= base;
        base %= MOD;
        ex >>= 1;
    }
    return rtn;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
//    cout << fixed << setprecision(15);
    // 二分探索
    // 全探索
    // 動的計画法
    // 逆からたどる
    // ネットワークフロー
    // 二部マッチング
    // ggrks
    /*----------------------------------------------------*/
    int n, m; cin >> n >> m;
    UnionFind uf(n);

    rep(_, m) {
        int ai, bi; cin >> ai >> bi;
        ai--; bi--;
        uf.unite(ai, bi);
    }

    rep(i, n) {
        if (uf.check(i)) {
            int a = uf.cnt.at(uf.root(i));
            print(mod_inv(fast_pow(2, a), 1000000007LL))
        } else {
            print(0)
        }
    }

//    rep(i, n) {
//        int root = uf.root(i);
//        if (root < 0) root = -root - 1;
//        print(uf.siz.at(root), uf.check(i))
//    }
    // 最大値は?
}
0