結果
問題 | No.1774 Love Triangle (Hard) |
ユーザー | 👑 hitonanode |
提出日時 | 2021-10-12 21:47:45 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 7,743 ms / 8,000 ms |
コード長 | 5,184 bytes |
コンパイル時間 | 5,094 ms |
コンパイル使用メモリ | 138,352 KB |
実行使用メモリ | 4,348 KB |
最終ジャッジ日時 | 2023-10-17 11:04:08 |
合計ジャッジ時間 | 450,722 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 3 ms
4,348 KB |
testcase_03 | AC | 46 ms
4,348 KB |
testcase_04 | AC | 3 ms
4,348 KB |
testcase_05 | AC | 13 ms
4,348 KB |
testcase_06 | AC | 2 ms
4,348 KB |
testcase_07 | AC | 123 ms
4,348 KB |
testcase_08 | AC | 2 ms
4,348 KB |
testcase_09 | AC | 1 ms
4,348 KB |
testcase_10 | AC | 1 ms
4,348 KB |
testcase_11 | AC | 72 ms
4,348 KB |
testcase_12 | AC | 2,404 ms
4,348 KB |
testcase_13 | AC | 588 ms
4,348 KB |
testcase_14 | AC | 175 ms
4,348 KB |
testcase_15 | AC | 623 ms
4,348 KB |
testcase_16 | AC | 925 ms
4,348 KB |
testcase_17 | AC | 4 ms
4,348 KB |
testcase_18 | AC | 648 ms
4,348 KB |
testcase_19 | AC | 6 ms
4,348 KB |
testcase_20 | AC | 51 ms
4,348 KB |
testcase_21 | AC | 30 ms
4,348 KB |
testcase_22 | AC | 6,020 ms
4,348 KB |
testcase_23 | AC | 6,029 ms
4,348 KB |
testcase_24 | AC | 6,126 ms
4,348 KB |
testcase_25 | AC | 6,001 ms
4,348 KB |
testcase_26 | AC | 6,075 ms
4,348 KB |
testcase_27 | AC | 6,112 ms
4,348 KB |
testcase_28 | AC | 6,089 ms
4,348 KB |
testcase_29 | AC | 6,237 ms
4,348 KB |
testcase_30 | AC | 6,108 ms
4,348 KB |
testcase_31 | AC | 6,094 ms
4,348 KB |
testcase_32 | AC | 6,062 ms
4,348 KB |
testcase_33 | AC | 6,110 ms
4,348 KB |
testcase_34 | AC | 6,163 ms
4,348 KB |
testcase_35 | AC | 6,095 ms
4,348 KB |
testcase_36 | AC | 5,987 ms
4,348 KB |
testcase_37 | AC | 6,184 ms
4,348 KB |
testcase_38 | AC | 5,983 ms
4,348 KB |
testcase_39 | AC | 6,082 ms
4,348 KB |
testcase_40 | AC | 6,061 ms
4,348 KB |
testcase_41 | AC | 6,166 ms
4,348 KB |
testcase_42 | AC | 6,239 ms
4,348 KB |
testcase_43 | AC | 6,212 ms
4,348 KB |
testcase_44 | AC | 6,208 ms
4,348 KB |
testcase_45 | AC | 6,178 ms
4,348 KB |
testcase_46 | AC | 6,180 ms
4,348 KB |
testcase_47 | AC | 6,112 ms
4,348 KB |
testcase_48 | AC | 6,172 ms
4,348 KB |
testcase_49 | AC | 6,189 ms
4,348 KB |
testcase_50 | AC | 6,198 ms
4,348 KB |
testcase_51 | AC | 6,352 ms
4,348 KB |
testcase_52 | AC | 7,743 ms
4,348 KB |
testcase_53 | AC | 6,234 ms
4,348 KB |
testcase_54 | AC | 6,229 ms
4,348 KB |
testcase_55 | AC | 6,101 ms
4,348 KB |
testcase_56 | AC | 6,194 ms
4,348 KB |
testcase_57 | AC | 6,210 ms
4,348 KB |
testcase_58 | AC | 6,164 ms
4,348 KB |
testcase_59 | AC | 6,222 ms
4,348 KB |
testcase_60 | AC | 6,200 ms
4,348 KB |
testcase_61 | AC | 6,191 ms
4,348 KB |
testcase_62 | AC | 6,482 ms
4,348 KB |
testcase_63 | AC | 6,422 ms
4,348 KB |
testcase_64 | AC | 6,263 ms
4,348 KB |
testcase_65 | AC | 6,356 ms
4,348 KB |
testcase_66 | AC | 6,395 ms
4,348 KB |
testcase_67 | AC | 6,209 ms
4,348 KB |
testcase_68 | AC | 6,392 ms
4,348 KB |
testcase_69 | AC | 6,436 ms
4,348 KB |
testcase_70 | AC | 6,213 ms
4,348 KB |
testcase_71 | AC | 6,462 ms
4,348 KB |
testcase_72 | AC | 6,379 ms
4,348 KB |
testcase_73 | AC | 6,369 ms
4,348 KB |
testcase_74 | AC | 6,420 ms
4,348 KB |
testcase_75 | AC | 6,415 ms
4,348 KB |
testcase_76 | AC | 6,283 ms
4,348 KB |
testcase_77 | AC | 6,446 ms
4,348 KB |
testcase_78 | AC | 6,382 ms
4,348 KB |
testcase_79 | AC | 6,161 ms
4,348 KB |
testcase_80 | AC | 6,404 ms
4,348 KB |
testcase_81 | AC | 6,435 ms
4,348 KB |
testcase_82 | AC | 5,945 ms
4,348 KB |
testcase_83 | AC | 5,971 ms
4,348 KB |
testcase_84 | AC | 5,955 ms
4,348 KB |
testcase_85 | AC | 5,916 ms
4,348 KB |
testcase_86 | AC | 6,012 ms
4,348 KB |
testcase_87 | AC | 5,746 ms
4,348 KB |
testcase_88 | AC | 5,639 ms
4,348 KB |
testcase_89 | AC | 5,656 ms
4,348 KB |
testcase_90 | AC | 5,167 ms
4,348 KB |
testcase_91 | AC | 4,888 ms
4,348 KB |
testcase_92 | AC | 5,109 ms
4,348 KB |
ソースコード
#include <algorithm> #include <cassert> #include <iostream> #include <random> #include <tuple> #include <vector> using namespace std; mt19937 mt(1967176539); // Berlekamp–Massey algorithm // https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm // Complexity: O(N^2) // input: S = sequence from field K // return: L = degree of minimal polynomial, // C_reversed = monic min. polynomial (size = L + 1, reversed order, C_reversed[0] = 1)) // Formula: convolve(S, C_reversed)[i] = 0 for i >= L // Example: // - [1, 2, 4, 8, 16] -> (1, [1, -2]) // - [1, 1, 2, 3, 5, 8] -> (2, [1, -1, -1]) // - [0, 0, 0, 0, 1] -> (5, [1, 0, 0, 0, 0, 998244352]) (mod 998244353) // - [] -> (0, [1]) // - [0, 0, 0] -> (0, [1]) // - [-2] -> (1, [1, 2]) template <typename Tfield> std::pair<int, std::vector<Tfield>> find_linear_recurrence(const std::vector<Tfield> &S) { int N = S.size(); using poly = std::vector<Tfield>; poly C_reversed{1}, B{1}; int L = 0, m = 1; Tfield b = 1; // adjust: C(x) <- C(x) - (d / b) x^m B(x) auto adjust = [](poly C, const poly &B, Tfield d, Tfield b, int m) -> poly { C.resize(std::max(C.size(), B.size() + m)); Tfield a = d / b; for (unsigned i = 0; i < B.size(); i++) C[i + m] -= a * B[i]; return C; }; for (int n = 0; n < N; n++) { Tfield d = S[n]; for (int i = 1; i <= L; i++) d += C_reversed[i] * S[n - i]; if (d == 0) m++; else if (2 * L <= n) { poly T = C_reversed; C_reversed = adjust(C_reversed, B, d, b, m); L = n + 1 - L; B = T; b = d; m = 1; } else C_reversed = adjust(C_reversed, B, d, b, m++); } return std::make_pair(L, C_reversed); } template <typename ModInt> std::vector<ModInt> gen_random_vector(int len) { static std::uniform_int_distribution<int> rnd(1, ModInt::mod() - 1); std::vector<ModInt> ret(len); for (auto &x : ret) x = rnd(mt); return ret; }; // Sparse matrix template <typename Tp> struct sparse_matrix { int H, W; std::vector<std::vector<std::pair<int, Tp>>> vals; sparse_matrix(int H = 0, int W = 0) : H(H), W(W), vals(H) {} int height() const { return H; } int width() const { return W; } void add_element(int i, int j, Tp val) { assert(i >= 0 and i < H); assert(j >= 0 and i < W); vals[i].emplace_back(j, val); } std::vector<Tp> prod(const std::vector<Tp> &vec) const { assert(W == int(vec.size())); std::vector<Tp> ret(H); for (int i = 0; i < H; i++) { for (const auto &p : vals[i]) ret[i] += p.second * vec[p.first]; } return ret; } }; template <class Matrix, class Tp> int blackbox_rank(const Matrix &M) { assert(M.height() == M.width()); const int N = M.height(); std::vector<Tp> b = gen_random_vector<Tp>(N), u = gen_random_vector<Tp>(N), D = gen_random_vector<Tp>(N); std::vector<Tp> uMDib(2 * N); for (int i = 0; i < 2 * N; i++) { uMDib[i] = std::inner_product(u.begin(), u.end(), b.begin(), Tp(0)); for (int j = 0; j < N; j++) b[j] *= D[j]; b = M.prod(b); } return find_linear_recurrence<Tp>(uMDib).first - 1; } #include <atcoder/modint> using mint = atcoder::static_modint<(1 << 30) + 3>; uniform_int_distribution<int> rndgen(0, mint::mod()); vector<int> solve(int r, const vector<tuple<int, int, int>> &uvws) { const int m = uvws.size(); vector<int> ret(m); ret[0] = 1; { sparse_matrix<mint> mat(r, r); for (int i = 0; i < m; ++i) { auto [u, v, w] = uvws[i]; mint x = rndgen(mt); mat.add_element(u, v, x); mat.add_element(v, w, x); mat.add_element(w, u, x); mat.add_element(v, u, -x); mat.add_element(w, v, -x); mat.add_element(u, w, -x); if (ret[i] or ret[i - 1]) continue; int rank = blackbox_rank<sparse_matrix<mint>, mint>(mat); ret[i] = rank / 2; } } { sparse_matrix<mint> mat(r, r); for (int i = 0; i < m; ++i) { auto [u, v, w] = uvws[i]; mint x = rndgen(mt); mat.add_element(u, v, x); mat.add_element(v, w, x); mat.add_element(w, u, x); mat.add_element(v, u, -x); mat.add_element(w, v, -x); mat.add_element(u, w, -x); if (ret[i]) continue; if (ret[i - 1] + 2 == ret[i + 1]) ret[i] = ret[i - 1] + 1; if (ret[i - 1] == ret[i + 1]) ret[i] = ret[i - 1]; if (ret[i]) continue; int rank = blackbox_rank<sparse_matrix<mint>, mint>(mat); ret[i] = rank / 2; } } return ret; } int main() { int N, M; cin >> N >> M; vector<tuple<int, int, int>> uvws; while (M--) { int u, v, w; cin >> u >> v >> w; u--, v--, w--; uvws.emplace_back(u, v, w); } auto ret = solve(N, uvws); for (auto x : ret) cout << x << '\n'; }