Submission #66760583

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifdef INCLUDED_MAIN
int main() {
    fast();
    int n,m;
    cin >> n >> m;
    vector<vector<pll>> graph(n);
    rep(i,0,m){
        int a,b,w;
        cin >> a >> b >> w;
        a--; b--;
        graph[a].push_back({b,w});
    }
    vector<ll> d(n, 0);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#ifdef INCLUDED_MAIN




int main() {
    fast();

    int n,m;
    cin >> n >> m;
    vector<vector<pll>> graph(n);


    rep(i,0,m){
        int a,b,w;
        cin >> a >> b >> w;
        a--; b--;
        graph[a].push_back({b,w});
    }

    vector<ll> d(n, 0);
    vector<bool> vis(n,0);
    queue<int> que;
    vis[0] = 1;
    que.push(0);

    while (!que.empty()) {
        int i = que.front();
        que.pop();
        for (auto &[v,w] : graph[i]) {
            if (!vis[v]) {
                vis[v] = true;
                d[v] = d[i] ^ w;
                que.push(v);
            }
        }
    }
    if(!vis[n-1]){
        cout << -1 << endl;
        return 0;
    }
    vector<ll> base(60,0);

    rep(i,0,n){
        for(auto &[j,w] : graph[i]){
            ll cycle = d[i] ^ d[j] ^ w;

            for(int b = 59; b >= 0; b--){
                if((cycle >> b) & 1){
                    if(base[b] == 0){
                        base[b] = cycle;
                        break;
                    }else{
                        cycle ^= base[b];
                    }
                }
            }
        }
    }

    ll ans = d[n-1];
    for(int b = 59; b >= 0; b--){
        if((ans >> b) & 1){
            if(base[b] != 0){
                ans ^= base[b];
            }
        }
    }

    cout << ans << endl;

}

#else
#pragma clang optimize on
#include <bits/stdc++.h>

//*
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/irange.hpp>
#include <boost/dynamic_bitset.hpp>
#include <boost/dynamic_bitset_fwd.hpp>
#include <boost/algorithm/string/replace.hpp>

using immense = boost::multiprecision::cpp_int;
#define sorta(v) boost::sort(v)
#define bs boost::dynamic_bitset<>
#define irange(s,e,step) boost::irange(s,e,step)
//*/

#include <atcoder/all>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = array<int, 2>;
using pll = array<ll,2>;
template<class T> using pq = priority_queue<T,vector<T>>;
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
using modint107 = atcoder::modint1000000007;


using ld = long double;

void fast(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
}

#define INF 1000390039
#define LLINF 1000000039000000039
#define IMAX INT_MAX
#define IMIN INT_MIN
#define LLMAX LONG_LONG_MAX
#define LLMIN LONG_LONG_MIN
#define inr(l, x, r) (l <= x and x < r)
#define einr(l, x, r) (l <= x and x <= r)
#define rep(i, a, b) for(ll i = (a); i < (b); i++)
#define erep(i, a, b) for(ll i = (a); i <= (b); i++)
#define rrep(i, a, b) for(ll i = (a); i >= (b); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pcnt(x) __builtin_popcount(x)
#define llpcnt(x) __builtin_popcountll(x)

#define vv(name, type, a, ...) vector<vector<type>> name(a, vector<type>(__VA_ARGS__))
#define vvv(name, type, a, b, ...) vector<vector<vector<type>>> name(a, vector<vector<type>>(b, vector<type>(__VA_ARGS__)))
#define vvvv(name, type, a, b, c, ...) vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
#define vvvvv(name, type, a, b, c, d, ...) vector<vector<vector<vector<vector<type>>>>> name(a, vector<vector<vector<vector<type>>>>(b, vector<vector<vector<type>>>(c, vector<vector<type>>(d, vector<type>(__VA_ARGS__)))));
#define v2l vector<vector<ll>>
//clock-wise rotate
#define vvl_kaiten(v) {int n = v.size(); vector<vector<long long>> nx(n, vector<long long>(n)); rep(i, 0, n) rep(j, 0, n) nx[j][n-i-1] = v[i][j]; swap(nx, v); }
//clock-wise rotate
#define kaiten(v) {int n = v.size(); vector<string> nx(n, string(n, '.')); rep(i, 0, n) rep(j, 0, n) nx[j][n-i-1] = v[i][j]; swap(nx, v); }

#define YES cout<<"Yes"<<endl
#define NO cout<<"No"<<endl
#define YN {cout<<"Yes"<<endl}else{cout<<"No"<<endl;}
#define NEIN cout<<"-1"<<endl
#ifndef ONLINE_JUDGE
    #define _GLIBCXX_DEBUG
    #define debug(...) debug_func(0, #__VA_ARGS__, __VA_ARGS__)
    
#else
    #define debug(...) 
#endif

template <typename T>
void debug_func(int cnt, T name) {
    (void)cnt;
    (void)name;
    cerr << endl;
}
template <typename T1, typename T2, typename... T3>
void debug_func(int i, const T1 &name, const T2 &a, const T3 &...b) {
    for ( ; name[i] != ',' && name[i] != '\0'; i++ ) cerr << name[i];
    cerr << ":" << a << " ";
    debug_func(i + 1, name, b...);
}


// 最大値・最小値の更新
template <typename T1, typename T2>
bool chmax(T1 &a, const T2& b){
    if(a < b){ a = b; return 1; }
    else return 0;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2& b){
    if(a > b){ a = b; return 1; }
    else return 0;
}

//vector入出力
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
    for (int i = 0; i < (int)v.size(); i++)
        os << v[i] << (i + 1 != (int)v.size() ? " " : "");
    return os;
}
template <typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
    for (T &in : v)
        is >> in;
    return is;
}

//128bit整数
using LL = __int128_t;

// 入力
inline std::istream& operator>>(std::istream& is, LL& x) {
    std::string s;
    is >> s;
    bool neg = !s.empty() && s[0] == '-';
    x = 0;
    for (char c : s.substr(neg ? 1 : 0))
        x = x * 10 + (c - '0');
    if (neg) x = -x;
    return is;
}

// 出力
inline std::ostream& operator<<(std::ostream& os, LL x) {
    if (x == 0) return os << '0';
    if (x < 0) { os << '-'; x = -x; }
    char buf[40];
    int len = 0;
    while (x > 0) {
        buf[len++] = char('0' + (x % 10));
        x /= 10;
    }
    while (len--) os << buf[len];
    return os;
}


/**
 *@brief xのn乗
 */
template<typename T,typename U>
ll intpow(T x, U n) {
    ll ret = 1;
    while (n > 0) {
        if (n & 1) ret = ret * x;
        x = x * x;
        n >>= 1;
    }
    return ret;
}

/**
 *@brief 平方数かを判定し、平方数ならその平方根を返す
 *@return 平方数ならその平方根、そうでなければ0
 *@note xは非負整数
 */
template<typename T>
T intsqrt(T x){
    T l = 0, r = x;
    while(r - l > 1){
        ll m = (l + r) / 2;
        if(m * m <= x)l = m;
        else r = m;
    }
    if(l*l != x)return 0;
    return l;
}
/**
 *@brief xのn乗 modulo
 */
template<typename T,typename U,typename V>
ll modpow(T x,U n,V Modulo) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % Modulo;
        x = x * x % Modulo;
        n >>= 1;
    }
    return res;
}

/**
 *@brief エウクレイデスの互助法による素因数分解
 *@return array<因数, 次数>がvectorに昇順で格納　1なら空
 */
vector< array<ll,2> > prime_factorize(ll N) {
    vector< array<ll,2> > res;
    for (ll a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        ll ex = 0;
        while (N % a == 0) {
            ++ex;
            N /= a;
        }
        res.push_back({a,ex});
    }
    if (N != 1) res.push_back({N,1});
    return res;
}


template <int char_size, int base>
struct Trie {
    /** 
     * @brief Trie のノード構造体
     */
    struct Node {
        vector<int> next;    ///< 子ノードへのインデックス（存在しなければ -1）
        vector<int> accept;  ///< このノードで終端となる単語の ID リスト
        int c;               ///< このノードに対応する文字コード (word[i] - base)
        int common;          ///< このノードを通過する単語数

        /**
         * @brief ノードを初期化する
         * @param c_ このノードに対応する文字コード
         */
        explicit Node(int c_) : next(char_size, -1), c(c_), common(0) {}
    };

    vector<Node> nodes;  ///< ノード一覧
    int root;            ///< 根ノードのインデックス (常に 0)

    /**
     * @brief コンストラクタ
     */
    Trie() : nodes(), root(0) {
        nodes.emplace_back(root);
    }

    /**
     * @brief 単語を挿入する
     * @param word 挿入する文字列
     * @param word_id 単語の識別 ID
     */
    void insert(const string &word, int word_id) {
        int node_id = root;
        for (char ch : word) {
            int ci = ch - base;
            int &nxt = nodes[node_id].next[ci];
            if (nxt == -1) {
                nxt = nodes.size();
                nodes.emplace_back(ci);
            }
            nodes[node_id].common++;
            node_id = nxt;
        }
        nodes[node_id].common++;
        nodes[node_id].accept.push_back(word_id);
    }

    /**
     * @brief 単語を挿入する（ID 自動付番版）
     * @param word 挿入する文字列
     */
    void insert(const string &word) {
        insert(word, nodes[root].common);
    }

    /**
     * @brief 完全一致または接頭辞検索
     * @param word 検索する文字列
     * @param prefix 接頭辞検索モードなら true
     * @return 見つかれば true、なければ false
     */
    bool search(const string &word, bool prefix = false) const {
        int node_id = root;
        for (char ch : word) {
            int ci = ch - base;
            int nxt = nodes[node_id].next[ci];
            if (nxt == -1) return false;
            node_id = nxt;
        }
        return prefix || !nodes[node_id].accept.empty();
    }

    /**
     * @brief 接頭辞を持つ単語が一つでもあるかを判定する
     * @param prefix 検索する接頭辞
     * @return 存在すれば true
     */
    bool has_prefix_word(const string &prefix) const {
        int node_id = root;
        for (char ch : prefix) {
            int ci = ch - base;
            if (ci < 0 || ci >= char_size) return false;
            int nxt = nodes[node_id].next[ci];
            if (nxt == -1) return false;
            node_id = nxt;
            if (!nodes[node_id].accept.empty()) return true;
        }
        return false;
    }

    /**
     * @brief 指定した接頭辞以下のすべての単語を削除する
     * @param prefix 削除対象の接頭辞
     * @return 削除した単語数
     */
    int erase_prefix(const string &prefix) {
        int node_id = root;
        vector<int> path;
        for (char ch : prefix) {
            int ci = ch - base;
            if (ci < 0 || ci >= char_size) return 0;
            int nxt = nodes[node_id].next[ci];
            if (nxt == -1) return 0;
            path.push_back(node_id);
            node_id = nxt;
        }

        int removed = nodes[node_id].common;
        if (removed == 0) return 0;

        queue<int> que;
        que.push(node_id);
        while (!que.empty()) {
            int v = que.front(); que.pop();
            nodes[v].common = 0;
            nodes[v].accept.clear();
            for (int nxt : nodes[v].next)
                if (nxt != -1) que.push(nxt);
        }

        for (int v : path)
            nodes[v].common -= removed;
        return removed;
    }

    /**
     * @brief 接頭辞を共有する単語数を返す
     * @param prefix 検索する接頭辞
     * @return 接頭辞を共有する単語数
     */
    int start_with(const string &prefix) const {
        int node_id = root;
        for (char ch : prefix) {
            int ci = ch - base;
            if (ci < 0 || ci >= char_size) return 0;
            int nxt = nodes[node_id].next[ci];
            if (nxt == -1) return 0;
            node_id = nxt;
        }
        return nodes[node_id].common;
    }

    /**
     * @brief 挿入した単語の総数を返す
     * @return 単語数
     */
    int count() const {
        return nodes[root].common;
    }

    /**
     * @brief ノード数を返す
     * @return ノード数
     */
    int size() const {
        return nodes.size();
    }
};

//Union-Find木
class UnionFind {
    public:
        UnionFind() = default;
    
        /// @brief Union-Find 木を構築します。
        explicit UnionFind(size_t n)
            : m_parentsOrSize(n, -1) {}
    
        /// @brief 頂点 i の root のインデックスを返します。
        int find(int i){
            if (m_parentsOrSize[i] < 0)return i;
            return (m_parentsOrSize[i] = find(m_parentsOrSize[i]));
        }
    
        /// @brief a のグループと b のグループを統合します。
        void merge(int a, int b){
            a = find(a);
            b = find(b);
            if (a != b){
                if (-m_parentsOrSize[a] < -m_parentsOrSize[b])std::swap(a, b);
                m_parentsOrSize[a] += m_parentsOrSize[b];
                m_parentsOrSize[b] = a;
            }
        }
    
        /// @brief a と b が同じグループに属すかを返します。
        bool connected(int a, int b){
            return (find(a) == find(b));
        }
    
        /// @brief i が属するグループの要素数を返します。
        int size(int i){
            return (-m_parentsOrSize[find(i)]);
        }
        vector<vector<int>> groups() {
            // member[v] := 要素 v をリーダーとするグループ
            vector<vector<int>> member(m_parentsOrSize.size());
            for (int v = 0; v < (int)m_parentsOrSize.size(); ++v) {
                member[find(v)].push_back(v);
            }
            
            // 配列 member の空の部分を削除したものを作る
            vector<vector<int>> res;
            for (int v = 0; v < (int)m_parentsOrSize.size(); ++v) {
                if (!member[v].empty()) res.push_back(member[v]);
            }
            return res;
        }
    
    private:
        // m_parentsOrSize[i] は i の 親,
        // ただし root の場合は (-1 * そのグループに属する要素数)
        vector<ll> m_parentsOrSize;
    };

#define INCLUDED_MAIN
#include __FILE__

#endif

Submission Info

Compile Error

Main.cpp:75: warning: ignoring ‘#pragma clang optimize’ [-Wunknown-pragmas]
   75 | #pragma clang optimize on
      | 

Judge Result