結果
| 問題 | No.2294 Union Path Query (Easy) |
| ユーザー |
 hitonanode
|
| 提出日時 | 2023-05-05 22:31:03 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 387 ms / 4,000 ms |
| コード長 | 14,019 bytes |
| コンパイル時間 | 2,910 ms |
| コンパイル使用メモリ | 203,532 KB |
| 実行使用メモリ | 39,680 KB |
| 最終ジャッジ日時 | 2024-11-23 09:25:06 |
| 合計ジャッジ時間 | 20,964 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 46 |
ソースコード
#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <chrono>#include <cmath>#include <complex>#include <deque>#include <forward_list>#include <fstream>#include <functional>#include <iomanip>#include <ios>#include <iostream>#include <limits>#include <list>#include <map>#include <numeric>#include <queue>#include <random>#include <set>#include <sstream>#include <stack>#include <string>#include <tuple>#include <type_traits>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>using namespace std;using lint = long long;using pint = pair<int, int>;using plint = pair<lint, lint>;struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;#define ALL(x) (x).begin(), (x).end()#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)#define REP(i, n) FOR(i,0,n)#define IREP(i, n) IFOR(i,0,n)template <typename T, typename V>void ndarray(vector<T>& vec, const V& val, int len) { vec.assign(len, val); }template <typename T, typename V, typename... Args> void ndarray(vector<T>& vec, const V& val, int len, Args... args) { vec.resize(len), for_each(begin(vec), end(vec), [&](T& v) { ndarray(v, val, args...); }); }template <typename T> bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; }template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; }const std::vector<std::pair<int, int>> grid_dxs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); }template <class T1, class T2> T1 floor_div(T1 num, T2 den) { return (num > 0 ? num / den : -((-num + den - 1) / den)); }template <class T1, class T2> std::pair<T1, T2> operator+(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first + r.first, l.second + r.second); }template <class T1, class T2> std::pair<T1, T2> operator-(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first - r.first, l.second - r.second); }template <class T> std::vector<T> sort_unique(std::vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; }template <class T> int arglb(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); }template <class T> int argub(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); }template <class IStream, class T> IStream &operator>>(IStream &is, std::vector<T> &vec) { for (auto &v : vec) is >> v; return is; }template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec);template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr);template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec);template <class OStream, class T, class U> OStream &operator<<(OStream &os, const pair<T, U> &pa);template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec);template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec);template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec);template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec);template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa);template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp);template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp);template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl);template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os <<']'; return os; }template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr) { os << '['; for (auto v : arr) os << v<< ','; os << ']'; return os; }template <class... T> std::istream &operator>>(std::istream &is, std::tuple<T...> &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);},tpl); return is; }template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl) { os << '('; std::apply([&os](auto &&... args) {((os << args << ','), ...);}, tpl); return os << ')'; }template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec) { os << '{'; for (auto v : vec) os<< v << ','; os << '}'; return os; }template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ','; os <<']'; return os; }template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}';return os; }template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os <<'}'; return os; }template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec) { os << '{'; for (auto v : vec) os << v <<','; os << '}'; return os; }template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa) { return os << '(' << pa.first << ',' << pa.second << ')'; }template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp) { os << '{'; for(auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }#ifdef HITONANODE_LOCALconst string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m";#define dbg(x) std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET<< std::endl#define dbgif(cond, x) ((cond) ? std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " <<__FILE__ << COLOR_RESET << std::endl : std::cerr)#else#define dbg(x) ((void)0)#define dbgif(cond, x) ((void)0)#endif#include <array>// Nimber (64 bit)// Reference:// - https://judge.yosupo.jp/submission/4542 (Original implementation idea)// - https://en.wikipedia.org/wiki/Nimber// - https://kyopro-friends.hatenablog.com/entry/2020/04/07/195850struct 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 >= yif (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;}();// UnionFind Tree (0-indexed), based on size of each disjoint setstruct UnionFind {std::vector<int> par, cou;UnionFind(int N = 0) : par(N), cou(N, 1) { iota(par.begin(), par.end(), 0); }int find(int x) { return (par[x] == x) ? x : (par[x] = find(par[x])); }bool unite(int x, int y) {x = find(x), y = find(y);if (x == y) return false;if (cou[x] < cou[y]) std::swap(x, y);par[y] = x, cou[x] += cou[y];return true;}int count(int x) { return cou[find(x)]; }bool same(int x, int y) { return find(x) == find(y); }std::vector<std::vector<int>> groups() {std::vector<std::vector<int>> ret(par.size());for (int i = 0; i < int(par.size()); ++i) ret[find(i)].push_back(i);ret.erase(std::remove_if(ret.begin(), ret.end(),[&](const std::vector<int> &v) { return v.empty(); }),ret.end());return ret;}};#include <numeric>#include <utility>#include <vector>// Weighted UnionFindtemplate <class S> struct WeightedUnionFind {std::vector<int> par, sz;std::vector<S> pot;WeightedUnionFind(int N = 0) : par(N), sz(N, 1), pot(N) {std::iota(par.begin(), par.end(), 0);}int find(int x) {if (par[x] != x) {int r = find(par[x]);pot[x] = pot[x] + pot[par[x]], par[x] = r;}return par[x];}bool unite(int s, int t, S rel_diff) {// Relate s and t by f[t] = f[s] + rel_diff// Return false iff contradiction happens.rel_diff = rel_diff + weight(s) + (-weight(t));if ((s = find(s)) == (t = find(t))) return rel_diff == 0;if (sz[s] < sz[t]) std::swap(s, t), rel_diff = -rel_diff;par[t] = s, sz[s] += sz[t], pot[t] = rel_diff;return true;}S weight(int x) { return find(x), pot[x]; }S diff(int s, int t) { return weight(t) + (-weight(s)); } // return f[t] - f[s]int count(int x) { return sz[find(x)]; }bool same(int s, int t) { return find(s) == find(t); }};constexpr int D = 30;struct S {// lint dist_sum = 0;int sz = 1;std::vector<int> dv0cnt;S() : dv0cnt(D) {}int dist_sum() const {__int128 ret = 0;REP(d, D) {lint n1 = dv0cnt.at(d), n0 = sz - dv0cnt.at(d);ret += __int128(n1 * n0) << d;}// dbg(make_tuple(sz, dv0cnt, ret));return ret % 998244353;}};int main() {int N;lint X;int Q;cin >> N >> X >> Q;WeightedUnionFind<Nimber> wuf(N);UnionFind uf(N);vector<S> components(N);// REP(i, N) components.at(i).vs.push_back(i);while (Q--) {int tp;cin >> tp;if (tp == 1) {int v;lint w;cin >> v >> w;wuf.unite(X, v, w);int s = uf.find(X), t = uf.find(v);uf.unite(s, t);if (uf.find(s) != s) swap(s, t);assert(uf.find(s) == s);w ^= wuf.diff(X, s).v ^ wuf.diff(t, v).v;REP(d, D) {if (((w >> d) & 1) == 0) components.at(s).dv0cnt.at(d) += components.at(t).dv0cnt.at(d);else components.at(s).dv0cnt.at(d) += components.at(t).sz - components.at(t).dv0cnt.at(d);}components.at(s).sz += components.at(t).sz;components.at(t) = S();} else if (tp == 2) {int u, v;cin >> u >> v;if (uf.same(u, v)) {auto d = wuf.diff(u, v);cout << d << '\n';X = (d.v + X) % N;} else {cout << -1 << '\n';}} else if (tp == 3) {int v;cin >> v;v = uf.find(v);cout << components.at(v).dist_sum() << '\n';} else if (tp == 4) {int value;cin >> value;X = (X + value) % N;}}}