Submission #66741047

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ull = unsigned long long int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pstr = pair<string, string>;
using ld = long double;
template <typename T>
using vc = vector<T>;
template <typename T>
using vvc = vector<vc<T>>;
template <typename T>
using vvvc = vector<vvc<T>>;
using vi = vc<int>;
using vl = vc<ll>;
template <class T, class S>
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ull = unsigned long long int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pstr = pair<string, string>;
using ld = long double;
template <typename T>
using vc = vector<T>;
template <typename T>
using vvc = vector<vc<T>>;
template <typename T>
using vvvc = vector<vvc<T>>;
using vi = vc<int>;
using vl = vc<ll>;
template <class T, class S>
inline bool chmax(T &a, const S &b) {
  return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
  return (a > b ? a = b, 1 : 0);
}

// macros
#define overload5(a, b, c, d, e, name, ...) name
#define overload4(a, b, c, d, name, ...) name
#define endl '\n'
#define REP0(n) for (ll i = 0; i < n; ++i)
#define REP1(i, n) for (ll i = 0; i < (n); ++i)
#define REP2(i, a, b) for (ll i = (a); i < (b); ++i)
#define REP3(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define rep(...) overload4(__VA_ARGS__, REP3, REP2, REP1, REP0)(__VA_ARGS__)
#define per0(n) for (int jidlsjf = 0; jidlsjf < (n); ++jidlsjf)
#define per1(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define per2(i, a, b) for (ll i = (a) - 1; i >= b; --i)
#define per3(i, a, b, c) for (ll i = (a) - 1; i >= (b); i -= (c))
#define per(...) overload4(__VA_ARGS__, per3, per2, per1, per0)(__VA_ARGS__)
#define fore0(a) rep(a.size())
#define fore1(i, a) for (auto &&i : a)
#define fore2(a, b, v) for (auto &&[a, b] : v)
#define fore3(a, b, c, v) for (auto &&[a, b, c] : v)
#define fore4(a, b, c, d, v) for (auto &&[a, b, c, d] : v)
#define fore(...) \
  overload5(__VA_ARGS__, fore4, fore3, fore2, fore1, fore0)(__VA_ARGS__)
#define pb push_back
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define drop(s) cout << #s << endl, exit(0)
#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define lbg(c, x) distance((c).begin(), lower_bound(all(c), (x), greater{}))
#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define ubg(c, x) distance((c).begin(), upper_bound(all(c), (x), greater{}))
#define all(c) begin(c), end(c)
#define rall(c) rbegin(c), rend(c)
#define SORT(v) sort(all(v))
#define REV(v) reverse(all(v))
#define REMOVE_DUPLICATES(v) SORT(v), v.erase(unique(all(v)), v.end())
#define IDX(c, x) (int)(distance((c).begin(), find(all(c), (x))))
template <typename T = ll, typename S>
T SUM(const S &v) {
  return accumulate(all(v), T(0));
}
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
constexpr pii dx4[4] = {pii{1, 0}, pii{0, 1}, pii{-1, 0}, pii{0, -1}};
constexpr pii dx8[8] = {{1, 0},  {1, 1},   {0, 1},  {-1, 1},
                        {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};
template <typename T>
bool out_grid(T i, T j, T h, T w) {
  return (!(0 <= i && i < h && 0 <= j && j < w));
}
namespace yesno_impl {
const string YESNO[2] = {"NO", "YES"};
const string YesNo[2] = {"No", "Yes"};
const string yesno[2] = {"no", "yes"};
const string firstsecond[2] = {"second", "first"};
const string FirstSecond[2] = {"Second", "First"};
const string possiblestr[2] = {"impossible", "possible"};
const string Possiblestr[2] = {"Impossible", "Possible"};
void YES(bool t = 1) { cout << YESNO[t] << "\n"; }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { cout << YesNo[t] << "\n"; }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { cout << yesno[t] << "\n"; }
void no(bool t = 1) { yes(!t); }
void first(bool t = 1) { cout << firstsecond[t] << "\n"; }
void First(bool t = 1) { cout << FirstSecond[t] << "\n"; }
void possible(bool t = 1) { cout << possiblestr[t] << "\n"; }
void Possible(bool t = 1) { cout << Possiblestr[t] << "\n"; }
};  // namespace yesno_impl
using namespace yesno_impl;

#define INT(...)   \
  int __VA_ARGS__; \
  IN(__VA_ARGS__)
#define INTd(...)  \
  int __VA_ARGS__; \
  IN2(__VA_ARGS__)
#define LL(...)   \
  ll __VA_ARGS__; \
  IN(__VA_ARGS__)
#define LLd(...)  \
  ll __VA_ARGS__; \
  IN2(__VA_ARGS__)
#define STR(...)      \
  string __VA_ARGS__; \
  IN(__VA_ARGS__)
#define CHR(...)    \
  char __VA_ARGS__; \
  IN(__VA_ARGS__)
#define DBL(...)      \
  double __VA_ARGS__; \
  IN(__VA_ARGS__)
#define VEC(type, name, size) \
  vector<type> name(size);    \
  IN(name)
#define VECd(type, name, size) \
  vector<type> name(size);     \
  IN2(name)
#define VEC2(type, name1, name2, size)   \
  vector<type> name1(size), name2(size); \
  for (int i = 0; i < size; i++) IN(name1[i], name2[i])
#define VEC2d(type, name1, name2, size)  \
  vector<type> name1(size), name2(size); \
  for (int i = 0; i < size; i++) IN2(name1[i], name2[i])
#define VEC3(type, name1, name2, name3, size)         \
  vector<type> name1(size), name2(size), name3(size); \
  for (int i = 0; i < size; i++) IN(name1[i], name2[i], name3[i])
#define VEC3d(type, name1, name2, name3, size)        \
  vector<type> name1(size), name2(size), name3(size); \
  for (int i = 0; i < size; i++) IN2(name1[i], name2[i], name3[i])
#define VEC4(type, name1, name2, name3, name4, size)               \
  vector<type> name1(size), name2(size), name3(size), name4(size); \
  for (int i = 0; i < size; i++) IN(name1[i], name2[i], name3[i], name4[i]);
#define VEC4d(type, name1, name2, name3, name4, size)              \
  vector<type> name1(size), name2(size), name3(size), name4(size); \
  for (int i = 0; i < size; i++) IN2(name1[i], name2[i], name3[i], name4[i]);
#define VV(type, name, h, w)                     \
  vector<vector<type>> name(h, vector<type>(w)); \
  IN(name)
#define VVd(type, name, h, w)                    \
  vector<vector<type>> name(h, vector<type>(w)); \
  IN2(name)
int scan() { return getchar(); }
void scan(int &a) { cin >> a; }
void scan(long long &a) { cin >> a; }
void scan(char &a) { cin >> a; }
void scan(double &a) { cin >> a; }
void scan(string &a) { cin >> a; }
template <class T, class S>
void scan(pair<T, S> &p) {
  scan(p.first), scan(p.second);
}
template <class T>
void scan(vector<T> &);
template <class T>
void scan(vector<T> &a) {
  for (auto &i : a) scan(i);
}
template <class T>
void scan(T &a) {
  cin >> a;
}
void IN() {}
void IN2() {}
template <class Head, class... Tail>
void IN(Head &head, Tail &...tail) {
  scan(head);
  IN(tail...);
}
template <class Head, class... Tail>
void IN2(Head &head, Tail &...tail) {
  scan(head);
  --head;
  IN2(tail...);
}

template <class T>
struct MaxFlow {
  struct _Edge {
    int to;
    T cap;
    _Edge(int _to, T _cap) : to(_to), cap(_cap) {}
  };
  int n;
  vc<_Edge> e;
  vvc<int> g;
  vi cur, h;
  MaxFlow() {}
  MaxFlow(int _n) { init(_n); }
  void init(int _n) {
    this->n = _n;
    e.clear();
    g.assign(_n, {});
    cur.resize(_n);
    h.resize(_n);
  }
  bool bfs(int s, int t) {
    h.assign(n, -1);
    queue<int> que;
    h[s] = 0;
    que.push(s);
    while (!que.empty()) {
      const int u = que.front();
      que.pop();
      fore(i, g[u]) {
        auto [v, c] = e[i];
        if (c > 0 && h[v] == -1) {
          h[v] = h[u] + 1;
          if (v == t) {
            return true;
          }
          que.push(v);
        }
      }
    }
    return false;
  }
  T dfs(int u, int t, T f) {
    if (u == t) {
      return f;
    }
    auto r = f;
    for (int &i = cur[u]; i < int(g[u].size()); ++i) {
      const int j = g[u][i];
      auto [v, c] = e[j];
      if (c > 0 && h[v] == h[u] + 1) {
        auto a = dfs(v, t, std::min(r, c));
        e[j].cap -= a;
        e[j ^ 1].cap += a;
        r -= a;
        if (r == 0) {
          return f;
        }
      }
    }
    return f - r;
  }
  void addEdge(int u, int v, T c) {
    g[u].emplace_back(e.size());
    e.emplace_back(v, c);
    g[v].emplace_back(e.size());
    e.emplace_back(u, 0);
  }
  T flow(int s, int t) {
    T ans = 0;
    while (bfs(s, t)) {
      cur.assign(n, 0);
      ans += dfs(s, t, std::numeric_limits<T>::max());
    }
    return ans;
  }
  std::vector<bool> minCut() {
    std::vector<bool> c(n);
    rep(i, n) { c[i] = (h[i] != -1); }
    return c;
  }
  struct Edge {
    int from;
    int to;
    T cap;
    T flow;
  };
  std::vector<Edge> edges() {
    std::vector<Edge> a;
    rep(i, ssize(e)) {
      Edge x;
      x.from = e[i + 1].to;
      x.to = e[i].to;
      x.cap = e[i].cap + e[i + 1].cap;
      x.flow = e[i + 1].cap;
      a.emplace_back(x);
    }
    return a;
  }
};

class Eratosthenes {
 public:
  vector<bool> isprime;
  vector<int> minfactor;
  vector<ll> primes;

  Eratosthenes(ll N) : isprime(N + 1, true), minfactor(N + 1, -1) {
    isprime[0] = isprime[1] = false;
    minfactor[1] = 1;

    rep(i, 2, N + 1) {
      if (!isprime[i]) continue;
      minfactor[i] = (int)i;
      primes.emplace_back(i);
      rep(j, i * 2, N + 1, i) {
        isprime[j] = false;
        if (minfactor[j] == -1) {
          minfactor[j] = (int)i;
        }
      }
    }
  }

  vc<pii> factorize(int n) {
    vc<pii> res;
    while (n > 1) {
      int p = minfactor[n];
      int exp = 0;

      while (minfactor[n] == p) {
        n /= p;
        ++exp;
      }
      res.emplace_back(p, exp);
    }
    return res;
  }

  vi divisors(int n) {
    vi res({1});

    auto pf = factorize(n);

    fore(p, pf) {
      int s = (int)ssize(res);
      rep(i, s) {
        int v = 1;
        rep(j, p.second) {
          v *= p.first;
          res.push_back(res[i] * v);
        }
      }
    }
    return res;
  }
};

class RLE {
 public:
  static vc<pair<char, ll>> encode(const std::string &input) {
    vc<pair<char, ll>> encoded;
    ll n = ssize(input);
    rep(i, n) {
      ll count = 1;
      while (i + 1 < n && input[i] == input[i + 1]) {
        ++count;
        ++i;
      }
      encoded.emplace_back(input[i], count);
    }
    return encoded;
  }

  static std::string decode(const std::string &input) {
    std::ostringstream decoded;
    ll n = ssize(input);
    rep(i, 0, n, 2) {
      char ch = input[i];
      ll count = input[i + 1] - '0';
      decoded << std::string(count, ch);
    }
    return decoded.str();
  }
};

template <typename T, typename S>
T ceil(T x, S y) {
  assert(y);
  return (y < 0 ? ceil(-x, -y) : (x > 0 ? (x + y - 1) / y : x / y));
}

template <typename T, typename S>
T floor(T x, S y) {
  assert(y);
  return (y < 0 ? floor(-x, -y)
                : (x > 0 ? x / y : x / y - (x % y == 0 ? 0 : 1)));
}

template <typename T>
void printMatrix(const vector<vector<T>> &matrix) {
  fore(row, matrix) {
    rep(j, (int)row.size()) {
      cout << row[j];
      if (j < (int)row.size() - 1) cout << " ";
    }
    cout << "\n";
  }
}

template <class T>
vvc<T> rotate90(const vvc<T> &matrix) {
  int M = (int)matrix.size();
  int N = (int)matrix[0].size();
  vvc<T> res(N, vc<T>(M));

  rep(i, M) rep(j, N) res[j][M - 1 - i] = matrix[i][j];
  return res;
}

template <class T>
vvc<T> rotate180(const vvc<T> &matrix) {
  int M = (int)matrix.size();
  int N = (int)matrix[0].size();
  vvc<T> res(M, vc<T>(N));

  rep(i, M) rep(j, N) res[M - 1 - i][N - 1 - j] = matrix[i][j];
  return res;
}

template <class T>
vvc<T> rotate270(const vvc<T> &matrix) {
  int M = (int)matrix.size();
  int N = (int)matrix[0].size();
  vvc<T> res(N, vc<T>(M));

  rep(i, M) rep(j, N) res[N - 1 - j][i] = matrix[i][j];
  return res;
}

template <typename T>
bool next_combination(const T first, const T last, int k) {
  const T subset = first + k;
  // empty container | k = 0 | k == n
  if (first == last || first == subset || last == subset) {
    return false;
  }
  T src = subset;
  while (first != src) {
    src--;
    if (*src < *(last - 1)) {
      T dest = subset;
      while (*src >= *dest) {
        dest++;
      }
      iter_swap(src, dest);
      rotate(src + 1, dest + 1, last);
      rotate(subset, subset + (last - dest) - 1, last);
      return true;
    }
  }
  // restore
  rotate(first, subset, last);
  return false;
}

template <class T>
T POW(T x, int n) {
  T res = 1;
  for (; n; n >>= 1, x *= x)
    if (n & 1) res *= x;
  return res;
}
template <class T, class S>
T POW(T x, S n, const ll &mod) {
  T res = 1;
  x %= mod;
  for (; n; n >>= 1, x = x * x % mod)
    if (n & 1) res = res * x % mod;
  return res;
}

void OUT() { cout << "\n"; }
template <class Head, class... Tail>
void OUT(const Head &head, const Tail &...tail) {
  cout << head;
  if (sizeof...(tail)) cout << ' ';
  OUT(tail...);
}

template <typename T>
static constexpr T inf = numeric_limits<T>::max() / 2;

struct Setup_io {
  Setup_io() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(0);
    cout << fixed << setprecision(15);
  }
} setup_io;

constexpr int BITS = 30;

int N, M;
vvc<pii> adj;
vvc<int> radj;
vc<bool> reachable_to_N, visited, inStack;
vector<int> dist_val;
int basis[BITS];

void add_basis(int x) {
  per(i, BITS) {
    if (!(x & (1 << i))) continue;
    if (!basis[i]) {
      basis[i] = x;
      return;
    }
    x ^= basis[i];
  }
}

void dfs(int u) {
  visited[u] = true;
  inStack[u] = true;
  fore(e, adj[u]) {
    int v = e.first;
    int w = e.second;
    if (!reachable_to_N[v]) continue;
    if (!visited[v]) {
      dist_val[v] = dist_val[u] ^ w;
      dfs(v);
    } else if (inStack[v]) {
      int cycle_xor = dist_val[u] ^ w ^ dist_val[v];
      add_basis(cycle_xor);
    }
  }
  inStack[u] = false;
}

int main() {
  cin >> N >> M;
  adj.assign(N + 1, {});
  radj.assign(N + 1, {});
  for (int i = 0; i < M; ++i) {
    int A, B, W;
    cin >> A >> B >> W;
    adj[A].emplace_back(B, W);
    radj[B].push_back(A);
  }

  reachable_to_N.assign(N + 1, false);
  {
    queue<int> q;
    reachable_to_N[N] = true;
    q.push(N);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int v : radj[u]) {
        if (!reachable_to_N[v]) {
          reachable_to_N[v] = true;
          q.push(v);
        }
      }
    }
  }

  visited.assign(N + 1, false);
  inStack.assign(N + 1, false);
  dist_val.assign(N + 1, 0);
  memset(basis, 0, sizeof(basis));

  if (reachable_to_N[1]) {
    dfs(1);
  }

  if (!visited[N]) {
    OUT(-1);
    return 0;
  }

  int res = dist_val[N];
  per(i, BITS) {
    if (basis[i] && ((res ^ basis[i]) < res)) {
      res ^= basis[i];
    }
  }

  OUT(res);
  return 0;
}

Submission Info

Judge Result