提出 #73136576

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define rep(i, s, e) for (ll i = (ll)(s); i < (ll)(e); ++i)
#define rrep(i, s ,e) for (ll i = (ll)(s); i > (ll)(e); --i)
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = 998244353;
//const ll MOD = 1000000007;

void solve(){
    ll n,m;cin >> n >> m;
    vector<vector<pair<ll,ll>>> g(n);
    rep(i,0,m){
        ll a,b,x;cin >> a >> b >> x;
        g[a-1].emplace_back(b-1,x);
        g[b-1].emplace_back(a-1,x);
    }
    vector<vector<ll>> v(25,vector<ll>(n,-1));
    vector<ll> A(25);
    rep(i,0,n+1){
        rep(j,0,25){
            A[j] += ((i>>j)&1);
        }
    }
    ll ans = 0;
    if(n%2 != 0){
        cout << -1 << endl;
        return;
    }
    rep(i,0,25){
        vector<ll> f(2);
        queue<ll> que;
        v[i][0] = 0;
        f[0]++;
        que.push(0);
        while(!que.empty()){
            ll V = que.front();que.pop();
            for(auto G:g[V]){
                auto [nv,x] = G;
                if(v[i][nv] != -1)continue;
                if((x>>i)&1){
                    v[i][nv] = 1-v[i][V]; 
                }
                else{
                    v[i][nv] = v[i][V];
                }
                f[v[i][nv]]++;
                que.push(nv); 
            }
        }
        if(f[0] < f[1])swap(f[0],f[1]);
        ans += ((A[i]-f[1])<<i);
    }
    cout << ans << endl;
    return;

}
int main(){
    cin.tie(0);cout.tie(0);
    ios_base::sync_with_stdio(false);

    ll t;cin >> t;
    while(t--){
        solve();
    }
}

提出情報

ジャッジ結果