結果

問題 No.1774 Love Triangle (Hard)
ユーザー hitonanode
提出日時 2021-10-02 10:19:45
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,352 bytes
コンパイル時間 1,830 ms
コンパイル使用メモリ 147,108 KB
実行使用メモリ 11,136 KB
最終ジャッジ日時 2024-09-16 04:48:09
合計ジャッジ時間 12,134 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 TLE * 1 -- * 80
権限があれば一括ダウンロードができます

ソースコード

diff # 

// ランクを M 回求める TLE になってほしい
// 乱択も一回だけ
#include <algorithm>
#include <cassert>
#include <chrono>
#include <iostream>
#include <numeric>
#include <random>
#include <utility>
#include <vector>
using namespace std;

#include <atcoder/modint>


// Try to calculate inverse of M and return rank of M (destructive)
template <class T>
int inverse_matrix(std::vector<std::vector<T>> &M) {
    const int N = M.size();
    assert(N and M[0].size() == M.size());
    std::vector<std::vector<T>> ret(N, std::vector<T>(N));
    for (int i = 0; i < N; ++i) ret[i][i] = 1;

    int rank = 0;
    for (int i = 0; i < N; ++i) {
        int ti = i;
        while (ti < N and M[ti][i] == 0) ti++;
        if (ti == N) {
            continue;
        }
        ++rank;
        ret[i].swap(ret[ti]), M[i].swap(M[ti]);
        T inv = T(1) / M[i][i];
        for (int j = 0; j < N; ++j) ret[i][j] *= inv;
        for (int j = i + 1; j < N; ++j) M[i][j] *= inv;
        for (int h = 0; h < N; ++h) {
            if (i == h) continue;
            const T c = -M[h][i];
            for (int j = 0; j < N; ++j) ret[h][j] += ret[i][j] * c;
            for (int j = i + 1; j < N; ++j) M[h][j] += M[i][j] * c;
        }
    }
    M = ret;
    return rank;
}

template <class ModInt>
vector<int> solve(int N, vector<pair<pair<int, int>, pair<int, int>>> bcs) {
    std::mt19937 mt(std::chrono::steady_clock::now().time_since_epoch().count());
    std::uniform_int_distribution<int> rng(0, ModInt::mod() - 1);

    std::vector<std::vector<ModInt>> M(N, std::vector<ModInt>(N)), Minv;

    vector<int> ret;
    for (auto [ab, cd] : bcs) {
        auto x = rng(mt);

        auto [a, b] = ab;
        auto [c, d] = cd;

        M[a][c] += x;
        M[a][d] -= x;
        M[b][c] -= x;
        M[b][d] += x;

        M[c][a] -= x;
        M[d][a] += x;
        M[c][b] += x;
        M[d][b] -= x;
        Minv = M;
        ret.push_back(inverse_matrix(Minv) / 2);
    }
    return ret;
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<pair<pair<int, int>, pair<int, int>>> edges;
    while (M--) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--, w--;
        edges.push_back({{u, w}, {v, w}});
    }
    auto ret = solve<atcoder::static_modint<1000000009>>(N, edges);
    for (auto x : ret) cout << x << '\n';
}
0