結果
問題 | No.408 五輪ピック |
ユーザー | hitonanode |
提出日時 | 2021-12-06 02:20:35 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 5,187 bytes |
コンパイル時間 | 1,039 ms |
コンパイル使用メモリ | 100,712 KB |
最終ジャッジ日時 | 2024-11-15 01:55:48 |
合計ジャッジ時間 | 2,178 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:135:14: error: 'std::tuple<int, int, Nimber> <structured bindings>' has incomplete type 135 | auto [s, t, w] = edges[e]; | ^~~~~~~~~ main.cpp:149:22: error: 'std::tuple<int, int, Nimber> <structured bindings>' has incomplete type 149 | auto [s, t, w] = edges[e]; | ^~~~~~~~~ In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/vector:64, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/random.h:34, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/random:49, from main.cpp:8: /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_vector.h: In instantiation of 'std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = std::tuple<int, int, Nimber>; _Alloc = std::allocator<std::tuple<int, int, Nimber> >]': /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_vector.h:526:7: required from here /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_vector.h:367:49: error: invalid use of incomplete type 'class std::tuple<int, int, Nimber>' 367 | _M_impl._M_end_of_storage - _M_impl._M_start); | ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~ In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:64, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/algorithm:60, from main.cpp:2: /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_pair.h:90:11: note: declaration of 'class std::tuple<int, int, Nimber>' 90 | class tuple; | ^~~~~ /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_vector.h: In instantiation of 'std::vector<_Tp, _Alloc>::size_type std::vector<_Tp, _Alloc>::s
ソースコード
#define PROBLEM "https://yukicoder.me/problems/no/408" #include <algorithm> #include <array> #include <cassert> #include <chrono> #include <iostream> #include <numeric> #include <random> #include <utility> #include <vector> using namespace std; // Nimber (64 bit) // Reference: // - https://en.wikipedia.org/wiki/Nimber // - https://kyopro-friends.hatenablog.com/entry/2020/04/07/195850 // - https://judge.yosupo.jp/submission/4542 (implementation idea) struct Nimber { using ull = unsigned long long; ull v; const static std::array<std::array<unsigned, 256>, 256> small_table; const static std::array<std::array<std::array<ull, 256>, 8>, 8> precalc; explicit operator bool() const { return v != 0; } Nimber(ull val = 0) : v(val) {} Nimber operator+(const Nimber &x) const { return Nimber(v ^ x.v); } Nimber operator-(const Nimber &x) const { return Nimber(v ^ x.v); } Nimber operator-() const { return *this; } Nimber &operator+=(const Nimber &x) { return *this = *this + x; } Nimber &operator-=(const Nimber &x) { return *this = *this + x; } template <class IStream> friend IStream &operator>>(IStream &is, Nimber &x) { ull v; return is >> v, x = Nimber(v), is; } template <class OStream> friend OStream &operator<<(OStream &os, const Nimber &x) { return os << x.v; } bool operator==(const Nimber &x) const { return v == x.v; } bool operator!=(const Nimber &x) const { return v != x.v; } bool operator<(const Nimber &x) const { return v < x.v; } static ull _rec(ull x, ull y) { if (x == 0 or y == 0) return 0; if (x < y) x ^= y, y ^= x, x ^= y; // Make x >= y if (y == 1) return x; for (int shift = 64 / 2;; shift >>= 1) { ull mask = (1ULL << shift) - 1; if (y >> shift) { ull v00 = _rec(x & mask, y & mask); ull v01 = _rec(x & mask, y >> shift); ull v10 = _rec(x >> shift, y & mask); ull v11 = _rec(x >> shift, y >> shift); return v00 ^ ((v01 ^ v10 ^ v11) << shift) ^ _rec(v11, 1ULL << (shift - 1)); } else if (x >> shift) { return (_rec(x >> shift, y) << shift) ^ _rec(x & mask, y); } } } Nimber operator*(const Nimber &x) const { ull ret = 0; for (int d = 0; d < 8; ++d) { for (int e = 0; e < 8; ++e) { ret ^= precalc[d][e][small_table[(v >> (d * 8)) & 255][(x.v >> (e * 8)) & 255]]; } } return Nimber(ret); } Nimber &operator*=(const Nimber &x) { return *this = *this * x; } }; const std::array<std::array<unsigned, 256>, 256> Nimber::small_table = []() { std::array<std::array<unsigned, 256>, 256> ret; for (int i = 0; i < 256; ++i) { for (int j = 0; j < 256; ++j) ret[i][j] = _rec(i, j); } return ret; }(); const std::array<std::array<std::array<unsigned long long, 256>, 8>, 8> Nimber::precalc = []() { std::array<std::array<std::array<unsigned long long, 256>, 8>, 8> ret; for (int d = 0; d < 8; ++d) { for (int e = 0; e < 8; ++e) { ull p = _rec(1ULL << (8 * d), 1ULL << (8 * e)); for (int i = 0; i < 256; ++i) ret[d][e][i] = _rec(p, i); } } return ret; }(); struct rand_int_ { using lint = long long; mt19937 mt; rand_int_() : mt(chrono::steady_clock::now().time_since_epoch().count()) {} lint operator()(lint x) { return this->operator()(0, x); } // [0, x) lint operator()(lint l, lint r) { uniform_int_distribution<lint> d(l, r - 1); return d(mt); } } rnd; int main() { cin.tie(nullptr), ios::sync_with_stdio(false); int N, M; cin >> N >> M; vector<tuple<int, int, Nimber>> edges; vector<vector<int>> eids(N + 1); while (M--) { int a, b; cin >> a >> b; --a, --b; Nimber w = rnd(1LL << 62); Nimber wn = rnd(1LL << 62); auto add_edge = [&](int s, int t, Nimber w) { int eid = edges.size(); eids[s].push_back(eid); edges.emplace_back(s, t, w); eids[t].push_back(eid + 1); edges.emplace_back(t, s, w); }; add_edge(a, b, w); if (a == 0) add_edge(b, N, wn); if (b == 0) add_edge(a, N, wn); } vector<Nimber> dp(edges.size()); for (int e = 0; e < int(edges.size()); ++e) { auto [s, t, w] = edges[e]; if (s == 0) dp[e] = w; } for (int t = 0; t < 4; ++t) { vector<Nimber> dpnxt(edges.size()); for (int now = 0; now < N; ++now) { Nimber sum = 0; for (auto e : eids[now]) { // e : now から出る // e ^ 1 : now に入る sum += dp[e ^ 1]; } for (auto e : eids[now]) { auto [s, t, w] = edges[e]; if (t != 0) dpnxt[e] += (sum - dp[e ^ 1]) * w; } } dp.swap(dpnxt); } for (auto e : eids[N]) { if (dp[e ^ 1]) { puts("YES"); return 0; } } puts("NO"); }