Submission #66766030

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("avx2,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <immintrin.h>
using namespace std;
using namespace __gnu_pbds;
// ==================== 基本定義 ====================
using ll   = long long;
using ull  = unsigned long long;
using ld   = long double;
using pii  = pair<int,int>;
using pll  = pair<ll,ll>;
using vi   = vector<int>;
using vll  = vector<ll>;
using vs   = vector<string>;
using vvll = vector<vll>;
using i128 = __int128;
using u128 = unsigned __int128;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("avx2,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <immintrin.h>
using namespace std;
using namespace __gnu_pbds;

// ==================== 基本定義 ====================
using ll   = long long;
using ull  = unsigned long long;
using ld   = long double;
using pii  = pair<int,int>;
using pll  = pair<ll,ll>;
using vi   = vector<int>;
using vll  = vector<ll>;
using vs   = vector<string>;
using vvll = vector<vll>;
using i128 = __int128;
using u128 = unsigned __int128;

constexpr ll INF64 = LLONG_MAX/4;
constexpr int MOD = 998244353;
constexpr ld  EPS = 1e-9;
constexpr ld  PI  = acosl(-1);

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

// ==================== 高速入出力 ====================
struct FastIO { FastIO(){ ios::sync_with_stdio(false); cin.tie(nullptr);} } fastio;

// ==================== マクロ ====================
#define rep(i,n)    for(ll i=0;i<(ll)(n);++i)
#define rep1(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define ALL(x)      (x).begin(),(x).end()
#define pb          push_back

// ==================== デバッグ ====================
#ifdef LOCAL
#define dbg(...) do{ fprintf(stderr,"[%s] = ",#__VA_ARGS__); _print(__VA_ARGS__); fprintf(stderr,"\n"); }while(0)
void _print(ll x){ fprintf(stderr,"%lld",x); }
void _print(int x){ fprintf(stderr,"%d",x); }
void _print(const string&s){ fprintf(stderr,"\"%s\"",s.c_str()); }
template<class T> void _print(const vector<T>&v){
    fprintf(stderr,"[");
    for(size_t i=0;i<v.size();++i){ _print(v[i]); if(i+1<v.size()) fprintf(stderr,","); }
    fprintf(stderr,"]");
}
template<class T,class U> void _print(const pair<T,U>&p){
    fprintf(stderr,"("); _print(p.first); fprintf(stderr,","); _print(p.second); fprintf(stderr,")");
}
#else
#define dbg(...)
#endif

// ==================== SIMD 加算 ====================
void simd_add(const vector<float>& a,const vector<float>& b,vector<float>& c){
    size_t n=a.size(); c.resize(n);
    size_t i=0;
    for(;i+8<=n;i+=8){
        __m256 va=_mm256_loadu_ps(&a[i]);
        __m256 vb=_mm256_loadu_ps(&b[i]);
        __m256 vc=_mm256_add_ps(va,vb);
        _mm256_storeu_ps(&c[i],vc);
    }
    for(;i<n;++i) c[i]=a[i]+b[i];
}

// ==================== 動的セグ木 ====================
struct DynSeg {
    struct Node{ ll val,lz; Node *l,*r; Node():val(0),lz(0),l(nullptr),r(nullptr){} };
    ll L,R; Node* root;
    DynSeg(ll _L,ll _R):L(_L),R(_R),root(new Node()){}
    void upd(Node*&nd,ll l,ll r,ll ql,ll qr,ll v){
        if(!nd) nd=new Node();
        if(ql<=l&&r<=qr){ nd->val+=(r-l+1)*v; nd->lz+=v; return; }
        ll m=(l+r)>>1;
        if(ql<=m) upd(nd->l,l,m,ql,qr,v);
        if(m<qr)  upd(nd->r,m+1,r,ql,qr,v);
        nd->val = (nd->l?nd->l->val:0)+(nd->r?nd->r->val:0)+nd->lz*(r-l+1);
    }
    ll qry(Node*nd,ll l,ll r,ll ql,ll qr){
        if(!nd||qr<l||r<ql) return 0;
        if(ql<=l&&r<=qr) return nd->val;
        ll m=(l+r)>>1,res=nd->lz*(min(r,qr)-max(l,ql)+1);
        res+=qry(nd->l,l,m,ql,qr)+qry(nd->r,m+1,r,ql,qr);
        return res;
    }
    void update(ll l,ll r,ll v){ upd(root,L,R,l,r,v); }
    ll query(ll l,ll r){ return qry(root,L,R,l,r); }
};

// ==================== mint ====================
struct mint {
    ll v;
    mint():v(0){}
    mint(ll _v){ v=_v%MOD; if(v<0) v+=MOD; }
    mint& operator+=(const mint&o){ if((v+=o.v)>=MOD) v-=MOD; return *this; }
    mint& operator-=(const mint&o){ if((v-=o.v)<0) v+=MOD; return *this; }
    mint& operator*=(const mint&o){ v=v*o.v%MOD; return *this; }
    friend mint operator+(mint a,const mint&b){ return a+=b; }
    friend mint operator-(mint a,const mint&b){ return a-=b; }
    friend mint operator*(mint a,const mint&b){ return a*=b; }
    mint pow(ll e)const{ mint r(1),b(*this); while(e){ if(e&1) r*=b; b*=b; e>>=1;} return r;}
    mint inv()const{ return pow(MOD-2); }
};

// ==================== 128bit 入出力 ====================
i128 read_i128(){
    string s; cin>>s;
    bool neg=false; int i=0;
    if(s[0]=='-'){ neg=true; i=1; }
    i128 x=0;
    for(;i<(int)s.size();++i) x=x*10+(s[i]-'0');
    return neg?-x:x;
}
void print_i128(i128 x){
    if(x==0){ cout<<0; return; }
    if(x<0){ cout<<'-'; x=-x; }
    string s;
    while(x){ s.push_back(char('0'+x%10)); x/=10; }
    reverse(ALL(s));
    cout<<s;
}

// ==================== 数学ユーティリティ ====================
ll gcd_ll(ll a,ll b){ while(b){ ll t=a%b; a=b; b=t;} return a; }
ll lcm_ll(ll a,ll b){ return a/gcd_ll(a,b)*b; }
ll ext_gcd(ll a,ll b,ll&x,ll&y){
    if(b==0){ x=1; y=0; return a; }
    ll x1,y1; ll g=ext_gcd(b,a%b,x1,y1);
    x=y1; y=x1-(a/b)*y1; return g;
}

// ==================== Rollback Union-Find ====================
struct RollbackUF {
    vector<int> d;
    vector<pair<int,int>> hist;
    RollbackUF(int n=0):d(n,-1){}

    int root(int x){ return d[x]<0?x:root(d[x]); }

    void unite(int x,int y){
        x=root(x); y=root(y);
        if(x==y) return;
        if(d[x]>d[y]) swap(x,y);
        hist.emplace_back(x,d[x]);
        hist.emplace_back(y,d[y]);
        d[x]+=d[y];
        d[y]=x;
    }

    void snapshot(){ hist.clear(); }
    void rollback(){
        while(!hist.empty()){
            auto [i,v]=hist.back(); hist.pop_back();
            d[i]=v;
        }
    }
};

// ==================== DSU ====================
struct DSU {
    vector<int> p;
    DSU(int n=0):p(n,-1){}
    int find(int x){ return p[x]<0?x:p[x]=find(p[x]); }
    bool unite(int a,int b){
        a=find(a); b=find(b);
        if(a==b) return false;
        if(p[a]>p[b]) swap(a,b);
        p[a]+=p[b]; p[b]=a;
        return true;
    }
};

// ==================== Fenwick ====================
struct Fenwick {
    int n; vll f;
    Fenwick(int _n=0):n(_n),f(n+1,0){}
    void add(int i,ll v){ for(++i;i<=n;i+=i&-i) f[i]+=v; }
    ll sum(int i){ ll s=0; for(++i;i>0;i-=i&-i) s+=f[i]; return s; }
    ll range(int l,int r){ return sum(r)-(l?sum(l-1):0); }
};

// ==================== SegTree (lazy) ====================
struct SegTree {
    int n; vector<ll> t,lz;
    SegTree(int _n=0){ n=1<<int(__lg(_n-1)+1); t.assign(2*n,0); lz.assign(2*n,0); }
    void apply(int i,ll v,int len){ t[i]+=v*len; lz[i]+=v; }
    void push(int i,int len){
        if(lz[i]){
            apply(2*i,  lz[i],len/2);
            apply(2*i+1,lz[i],len/2);
            lz[i]=0;
        }
    }
    void upd(int ql,int qr,ll v,int i,int l,int r){
        if(ql<=l&&r<=qr){ apply(i,v,r-l+1); return; }
        if(r<ql||qr<l) return;
        push(i,r-l+1);
        int m=(l+r)>>1;
        upd(ql,qr,v,2*i,  l,  m);
        upd(ql,qr,v,2*i+1,m+1,r);
        t[i]=t[2*i]+t[2*i+1];
    }
    ll qry(int ql,int qr,int i,int l,int r){
        if(ql<=l&&r<=qr) return t[i];
        if(r<ql||qr<l) return 0;
        push(i,r-l+1);
        int m=(l+r)>>1;
        return qry(ql,qr,2*i,  l,  m)
             + qry(ql,qr,2*i+1,m+1,r);
    }
    void update(int l,int r,ll v){ upd(l,r,v,1,0,n-1); }
    ll query(int l,int r){ return qry(l,r,1,0,n-1); }
};

// ==================== グラフアルゴリズム ====================
vector<vector<pll>> adjW;
vector<vector<int>>     adj;

vector<ll> bfs(int s){
    int N=adj.size();
    vector<ll> d(N,-1); queue<int>q;
    d[s]=0; q.push(s);
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int v:adj[u]){
            if(d[v]==-1){ d[v]=d[u]+1; q.push(v); }
        }
    }
    return d;
}

vector<ll> zero_one_bfs(int s){
    int N=adjW.size();
    vector<ll> d(N,INF64);
    deque<int> dq;
    d[s]=0; dq.push_front(s);
    while(!dq.empty()){
        int u=dq.front(); dq.pop_front();
        for(auto &e:adjW[u]){
            int v=e.first; ll w=e.second;
            if(d[v]>d[u]+w){
                d[v]=d[u]+w;
                if(w==0) dq.push_front(v);
                else     dq.push_back(v);
            }
        }
    }
    return d;
}

vector<ll> dijkstra(int s){
    int N=adjW.size();
    vector<ll> d(N,INF64);
    priority_queue<pll,vector<pll>,greater<>> pq;
    d[s]=0; pq.push({0,s});
    while(!pq.empty()){
        auto [du,u]=pq.top(); pq.pop();
        if(du!=d[u]) continue;
        for(auto &e:adjW[u]){
            int v=e.first; ll w=e.second;
            if(d[v]>du+w){
                d[v]=du+w; pq.push({d[v],v});
            }
        }
    }
    return d;
}

// ==================== Dinic 最大流 ====================
struct Dinic {
    int n,s,t;
    struct Edge{ int v; ll cap,flow; };
    vector<vector<int>> g;
    vector<Edge> edges;
    vector<int> level, ptr;
    Dinic(int _n=0):n(_n),g(n),level(n),ptr(n){}
    void addEdge(int u,int v,ll c){
        g[u].pb(edges.size());
        edges.push_back({v,c,0});
        g[v].pb(edges.size());
        edges.push_back({u,0,0});
    }
    bool bfs(){
        fill(level.begin(),level.end(),-1);
        queue<int>q; q.push(s); level[s]=0;
        while(!q.empty()){
            int u=q.front(); q.pop();
            for(int id:g[u]){
                auto &e=edges[id];
                if(level[e.v]<0 && e.flow<e.cap){
                    level[e.v]=level[u]+1;
                    q.push(e.v);
                }
            }
        }
        return level[t]>=0;
    }
    ll dfs(int u,ll pushed){
        if(!pushed||u==t) return pushed;
        for(int &cid=ptr[u];cid<(int)g[u].size();++cid){
            auto &e=edges[g[u][cid]];
            if(level[e.v]!=level[u]+1||e.flow>=e.cap) continue;
            ll tr=dfs(e.v,min(pushed,e.cap-e.flow));
            if(tr){
                e.flow+=tr;
                edges[g[u][cid]^1].flow-=tr;
                return tr;
            }
        }
        return 0;
    }
    ll maxflow(int S,int T){
        s=S; t=T; ll flow=0;
        while(bfs()){
            fill(ptr.begin(),ptr.end(),0);
            while(ll pushed=dfs(s,LLONG_MAX)) flow+=pushed;
        }
        return flow;
    }
};

// ==================== Pollard’s Rho ====================
ll modmul(ll a,ll b,ll m){ return (__int128)a*b%m; }
ll modpow(ll a,ll e,ll m){
    ll r=1; a%=m;
    while(e){ if(e&1) r=modmul(r,a,m); a=modmul(a,a,m); e>>=1; }
    return r;
}
bool isPrime(ll n){
    if(n<2) return false;
    for(ll p:{2,3,5,7,11,13,17,19,23,29,31})
        if(n%p==0) return n==p;
    ll d=n-1,s=0;
    while(!(d&1)){ d>>=1; ++s; }
    for(ll a:{2,325,9375,28178,450775,9780504,1795265022}){
        if(a%n==0) continue;
        ll x=modpow(a,d,n);
        if(x==1||x==n-1) continue;
        bool comp=true;
        rep(i,s-1){
            x=modmul(x,x,n);
            if(x==n-1){ comp=false; break; }
        }
        if(comp) return false;
    }
    return true;
}
ll pollard(ll n){
    if(n%2==0) return 2;
    ll x=uniform_int_distribution<ll>(2,n-2)(rng);
    ll y=x, c=uniform_int_distribution<ll>(1,n-1)(rng), d=1;
    while(d==1){
        x=(modmul(x,x,n)+c)%n;
        y=(modmul(y,y,n)+c)%n;
        y=(modmul(y,y,n)+c)%n;
        d=gcd_ll(abs(x-y),n);
    }
    return d==n?pollard(n):d;
}
void factorRec(ll n,vll&f){
    if(n<2) return;
    if(isPrime(n)){ f.pb(n); return; }
    ll d=pollard(n);
    factorRec(d,f);
    factorRec(n/d,f);
}
vll factor(ll n){
    vll f;
    factorRec(n,f);
    sort(ALL(f));
    return f;
}

// ==================== Manacher ====================
vll manacher(const string&s){
    ll n=s.size(); vll d1(n),d2(n);
    ll l=0,r=-1;
    rep(i,n){
        ll k=(i>r?1:min(d1[l+r-i],r-i+1));
        while(0<=i-k&&i+k<n&&s[i-k]==s[i+k]) ++k;
        d1[i]=k--; if(i+k>r){l=i-k; r=i+k;}
    }
    l=0; r=-1;
    rep(i,n){
        ll k=(i>r?0:min(d2[l+r-i+1],r-i+1));
        while(0<=i-k-1&&i+k<n&&s[i-k-1]==s[i+k]) ++k;
        d2[i]=k--; if(i+k>r){l=i-k-1;r=i+k;}
    }
    vll res(2*n);
    rep(i,n) res[2*i]=d1[i], res[2*i+1]=d2[i];
    return res;
}

// ==================== Eertree ====================
struct Eertree {
    struct Node { array<int,26> nxt; int link,len; Node(int L=0):link(0),len(L){ nxt.fill(0);} };
    vector<Node> tree; int last,sz; string s;
    Eertree(int n=0){ tree.reserve(n+5); tree.emplace_back(-1); tree.emplace_back(0);
        tree[0].link=0; tree[1].link=0; last=1; sz=2; s="";
    }
    void add_char(char ch){
        int c=ch-'a'; s+=ch;
        int pos=s.size()-1, cur=last;
        while(true){
            int L=tree[cur].len;
            if(pos-1-L>=0&&s[pos-1-L]==ch) break;
            cur=tree[cur].link;
        }
        if(tree[cur].nxt[c]){ last=tree[cur].nxt[c]; return; }
        tree.emplace_back(tree[cur].len+2);
        int nw=sz++; tree[cur].nxt[c]=nw;
        if(tree[nw].len==1){ tree[nw].link=1; last=nw; return; }
        while(true){
            cur=tree[cur].link; int L=tree[cur].len;
            if(pos-1-L>=0&&s[pos-1-L]==ch){
                tree[nw].link=tree[cur].nxt[c]; break;
            }
        }
        last=nw;
    }
    int size()const{return sz-2;}
};

// ==================== Sqrt Decomp ====================
struct SqrtDecomp {
    int n, sz; vll arr, block;
    SqrtDecomp(const vll&a){
        n=a.size(); sz=sqrt(n)+1; arr=a; block.assign(sz,0);
        rep(i,n) block[i/sz]+=arr[i];
    }
    void update(int idx,ll v){
        int b=idx/sz; block[b]+=v-arr[idx]; arr[idx]=v;
    }
    ll query(int l,int r){
        ll sum=0; int bl=l/sz, br=r/sz;
        if(bl==br) rep1(i,l,r+1) sum+=arr[i];
        else{
            int endb=(bl+1)*sz-1;
            rep1(i,l,endb+1) sum+=arr[i];
            rep1(b,bl+1,br) sum+=block[b];
            rep1(i,br*sz,r+1) sum+=arr[i];
        }
        return sum;
    }
};

// ==================== Mo’s Algorithm ====================
struct Mo {
    int n,B;
    vector<int> L,R,ord;
    vector<ll> ans;
    function<void(int)> add,rem;
    Mo(int _n=0):n(_n),B(sqrt(n)){}

    void init(const vector<pair<int,int>>&qs){
        int q=qs.size();
        L.resize(q); R.resize(q); ord.resize(q); ans.resize(q);
        rep(i,q){ L[i]=qs[i].first; R[i]=qs[i].second; ord[i]=i; }
        sort(ALL(ord),[&](int i,int j){
            if(L[i]/B!=L[j]/B) return L[i]<L[j];
            return ((L[i]/B)&1)?R[i]>R[j]:R[i]<R[j];
        });
    }
    void run(){
        int l=0,r=-1;
        for(int i:ord){
            while(r<R[i]) add(++r);
            while(l>L[i]) add(--l);
            while(r>R[i]) rem(r--);
            while(l<L[i]) rem(l++);
            ans[i]=1/* current answer state */;
        }
    }
};

// ==================== Main ====================
int main(){
    FastIO fastio;
    ll n, m;
    cin >> n >> m;
    vector<vector<pair<int,ll>>> g(n+1);
    rep(i, m){
        ll u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }
    vll d(n+1, -1), bs;
    d[1] = 0;
    vll st;
    vi ip;
    st.pb(1);
    ip.pb(0);
    while(!st.empty()){
        ll u = st.back();
        if(ip.back() < (int)g[u].size()){
            auto [v, w] = g[u][ip.back()++];
            ll nd = d[u] ^ w;
            if(d[v] == -1){
                d[v] = nd;
                st.pb(v);
                ip.pb(0);
            } else {
                ll x = nd ^ d[v];
                rep(j, bs.size()) x = min(x, x ^ bs[j]);
                if(x){
                    bs.pb(x);
                    sort(bs.rbegin(), bs.rend());
                }
            }
        } else {
            st.pop_back();
            ip.pop_back();
        }
    }
    if(d[n] == -1){
        cout << -1 << '\n';
        return 0;
    }
    ll ans = d[n];
    rep(j, bs.size()) ans = min(ans, ans ^ bs[j]);
    cout << ans << '\n';
    return 0;
}

Submission Info

Judge Result