Submission #66778262

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
#include <bits/stdc++.h>
using namespace std;
// define
#define fore(x, a) for (auto &x : a)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repp(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
// typedef
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
const double pi = 3.141592653589793238;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

// include
#include <bits/stdc++.h>
using namespace std;

// define
#define fore(x, a) for (auto &x : a)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repp(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

// typedef
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;

const double pi = 3.141592653589793238;
const int inf = 1073741823;
const ll infl = 1LL << 60;
const int mod = 998244353;
struct Init { Init() { ios::sync_with_stdio(0); cin.tie(0); } }init;

struct Edge {
    int to; 
    int cost;
    Edge(int t, ll c) : to(t), cost(c) {}
}; 

vector<vector<Edge>> adj; // 隣接リスト
vector<bool> visited;
vi xor_val; // 各ノードへのXOR値 予約語なのか？xorは使えなかった
int basis[60]; // XOR基底？っていうらしい

void insert_basis(ll mask) {
    for (int i = 59; i >= 0; i--) {
        if (!((mask >> i-1) & 1)) continue;
        if (!basis[i]) {
            basis[i] = mask;
            return;
        }
        mask ^= basis[i]; // 基底にある要素とXORを取る
    }
}

void dfs(int u, int current_xor) {
    visited[u] = true;
    xor_val[u] = current_xor;

    for (const auto& edge : adj[u]) {
        int v = edge.to;
        ll w = edge.cost;
        if (!visited[v]) {
            dfs(v, current_xor ^ w);
        } else {
            insert_basis(current_xor ^ w ^ xor_val[v]);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    adj.resize(n+1);
    visited.resize(n+1, false);
    xor_val.resize(n+1, 0);
    memset(basis, 0, sizeof(basis));

    rep(i, n) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(Edge(v, w));
    }

    dfs(1, 0);

    if (!visited[n]) {
        cout << -1 << endl;
    } else {
        ll path_xor = xor_val[n];

        for (int i = 59; i >= 0; i--) {
            if (basis[i]) { 
                path_xor = min(path_xor, path_xor ^ basis[i]);
            }
        }
        cout << path_xor << endl;
    }

    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void insert_basis(ll)’:
Main.cpp:40:25: warning: suggest parentheses around ‘-’ inside ‘>>’ [-Wparentheses]
   40 |         if (!((mask >> i-1) & 1)) continue;
      |                        ~^~

Judge Result