Submission #66749434

Source Code Expand

Copy
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
const int INF = INT_MAX;
const long long LINF = 1LL << 60;
const long long MOD1000000007 = 1000000007;
const long long MOD998244353 = 998244353;
using namespace std;
/*
   ##       ##       ####               ###
  ####      ##      ##  ##               ##
 ##  ##    #####   ##        ####        ##    ####    ######
 ##  ##     ##     ##       ##  ##    #####   ##  ##    ##  ##
 ######     ##     ##       ##  ##   ##  ##   ######    ##
 ##  ##     ## ##   ##  ##  ##  ##   ##  ##   ##        ##
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif

const int INF = INT_MAX;
const long long LINF = 1LL << 60;
const long long MOD1000000007 = 1000000007;
const long long MOD998244353 = 998244353;

using namespace std;

/*

   ##       ##       ####               ###
  ####      ##      ##  ##               ##
 ##  ##    #####   ##        ####        ##    ####    ######
 ##  ##     ##     ##       ##  ##    #####   ##  ##    ##  ##
 ######     ##     ##       ##  ##   ##  ##   ######    ##
 ##  ##     ## ##   ##  ##  ##  ##   ##  ##   ##        ##
 ##  ##      ###     ####    ####     ######   #####   ####

*/

/*---------------- typedef ----------------------*/

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

/*---------------- function ----------------------*/
template <class T>
bool clamp(T x, T min, T max) { return (x >= min and x <= max); }
#define YES cout << "Yes" << endl;
#define NO cout << "No" << endl;
void YesNo(bool ok) { cout << (ok ? "Yes" : "No") << endl; }
template <class T>
void chmin(T &a, const T &b)
{
    if (b < a)
        a = b;
}
template <class T>
void chmax(T &a, const T &b)
{
    if (a < b)
        a = b;
}

/*-------------- input stream ------------------*/
#ifdef __LOCAL
static istream *inputStream = &cin;
void inputTestCaseInLocal(string path)
{
    size_t pos = path.find_last_of("\\/");
    string fileName = (pos == string::npos ? path : path.substr(pos + 1));
    pos = fileName.find_last_of(".");
    if (pos != string::npos)
        fileName = fileName.substr(0, pos);
    static ifstream file("input/" + fileName + ".txt");
    if (file and file.peek() != ifstream::traits_type::eof())
        inputStream = &file;
}
void INPUT() {}
template <typename Head, typename... Tail>
void INPUT(Head &&head, Tail &&...tail)
{
    (*inputStream) >> head;
    INPUT(forward<Tail>(tail)...);
}
template <typename T, typename... Vectors>
void INPUT(std::vector<T> &first, std::vector<Vectors> &...rest)
{
    size_t size = first.size();
    for (size_t i = 0; i < size; ++i)
    {
        (*inputStream) >> first[i];
        (void)initializer_list<T>{((*inputStream) >> rest[i], 0)...};
    }
}
#else
void inputTestCaseInLocal([[maybe_unused]] string path) {}
void INPUT() {}
template <typename Head, typename... Tail>
void INPUT([[maybe_unused]] Head &&head, [[maybe_unused]] Tail &&...tail)
{
    cin >> head;
    INPUT(forward<Tail>(tail)...);
}
template <typename T, typename... Vectors>
void INPUT([[maybe_unused]] vector<T> &first, [[maybe_unused]] vector<Vectors> &...rest)
{
    size_t size = first.size();
    for (size_t i = 0; i < size; ++i)
    {
        cin >> first[i];
        (void)initializer_list<T>{(cin >> rest[i], 0)...};
    }
}
#endif

/*---------------- debug ---------------------*/

#ifdef __LOCAL
void views() { cout << endl; }
template <class Head, class... Tail>
void views([[maybe_unused]] Head &&head, [[maybe_unused]] Tail &&...tail)
{
    cout << head << " ";
    views(move(tail)...);
}
template <typename T>
void view(const std::vector<T> &v)
{
    for (const auto &e : v)
    {
        cout << e << " ";
    }
    cout << endl;
}
template <typename T>
void view(const vector<std::vector<T>> &vv)
{
    for (const auto &v : vv)
    {
        view(v);
    }
}
#else
template <class Head, class... Tail>
void view([[maybe_unused]] Head &&head, [[maybe_unused]] Tail &&...tail) {}
template <typename T>
void view([[maybe_unused]] T e) {}
template <typename T>
void view([[maybe_unused]] const vector<T> &v) {}
template <typename T>
void view([[maybe_unused]] const vector<vector<T>> &vv) {}
#endif

/*---------------- macro -------------------------*/

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, j, n) for (int i = j; i < (int)(n); i++)
#define revrep(i, n) for (int i = n; i >= 0; i--)
#define rrep(i, n) for (int i = 1; i <= (int)(n); i++)
#define rrep1(i, j, n) for (int i = j; i <= (int)(n); i++)
#define nfor(i, s, n) for (int i = s; i < n; i++)
#define dfor(i, s, n) for (int i = s - 1; i >= n; i--)
#define each(i, a) for (auto &&i : a)
#define bit(k) (1LL << (k))
#define all(x) (x).begin(), (x).end()
#define fill(x, y) memset(x, y, sizeof(x))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define SZ(a) int((a).size())
#define pb push_back
#define eb emplace_back
#define em emplace
#define pob pop_back
template <class T>
using pq = priority_queue<T, vector<T>>;
template <class T>
using pq_g = priority_queue<T, vector<T>, greater<T>>;

/*-------------- source code --------------------*/

// int dx[4] = {1, 0, -1, 0};
// int dy[4] = {0, 1, 0, -1};
// int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
// int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

void solve2()
{
}

int N, M;
vector<ll> A, B, W;
vector<pair<ll, ll>> g[1009];

void solve()
{
    cin >> N >> M;
    A.resize(M);
    B.resize(M);
    W.resize(M);
    rep(i, M)
    {
        cin >> A[i] >> B[i] >> W[i];
        g[A[i]].push_back({B[i], W[i]});
    }

    queue<ll> q;
    q.push(1);
    vector<ll> dist(N + 1, LINF);
    dist[1] = 0;

    ll basis[61] = {};
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (auto [v, w] : g[u])
        {
            ll x = dist[u] ^ w;
            if (dist[v] == LINF)
            {
                dist[v] = dist[u] ^ w;
                q.push(v);
            }
            else
            {
                ll cyc = x xor dist[v];
                for (int i = 60; i >= 0; --i)
                {
                    if (!(cyc >> i & 1))
                        continue;
                    if (!basis[i])
                    {
                        basis[i] = cyc;
                        break;
                    }
                    cyc ^= basis[i];
                }
            }
        }
    }

    if (dist[N] == LINF)
    {
        cout << -1 << "\n";
        return;
    }

    ll ans = dist[N];
    for (int i = 60; i >= 0; i--)
    {
        if ((ans ^ basis[i]) < ans)
        {
            ans = ans ^ basis[i];
        }
    }
    cout << ans << "\n";
}

int main([[maybe_unused]] int argc, [[maybe_unused]] char *argv[])
{
    // cout << fixed << setprecision(10);
    cin.tie(0)->sync_with_stdio(0);
    inputTestCaseInLocal(argv[0]);
    int t = 1;
    while (t--)
    {
        solve();
        // solve2();
    }

    return 0;
}

Submission Info

Submission Time
Task D - XOR Shortest Walk
User mn01137
Language C++ 20 (gcc 12.2)
Score 0
Code Size 6779 Byte
Status WA
Exec Time 2 ms
Memory 3688 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 3
AC × 30
WA × 3
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
hand_01.txt AC 1 ms 3496 KiB
hand_02.txt AC 1 ms 3632 KiB
hand_03.txt AC 1 ms 3424 KiB
hand_04.txt AC 1 ms 3568 KiB
hand_05.txt AC 1 ms 3492 KiB
hand_06.txt WA 1 ms 3560 KiB
hand_07.txt WA 1 ms 3420 KiB
hand_08.txt WA 1 ms 3552 KiB
random_01.txt AC 1 ms 3536 KiB
random_02.txt AC 2 ms 3592 KiB
random_03.txt AC 1 ms 3496 KiB
random_04.txt AC 1 ms 3668 KiB
random_05.txt AC 1 ms 3492 KiB
random_06.txt AC 1 ms 3584 KiB
random_07.txt AC 1 ms 3624 KiB
random_08.txt AC 1 ms 3540 KiB
random_09.txt AC 1 ms 3568 KiB
random_10.txt AC 2 ms 3564 KiB
random_11.txt AC 1 ms 3532 KiB
random_12.txt AC 2 ms 3588 KiB
random_13.txt AC 2 ms 3584 KiB
random_14.txt AC 1 ms 3528 KiB
random_15.txt AC 1 ms 3636 KiB
random_16.txt AC 2 ms 3588 KiB
random_17.txt AC 2 ms 3616 KiB
random_18.txt AC 2 ms 3652 KiB
random_19.txt AC 2 ms 3504 KiB
random_20.txt AC 2 ms 3688 KiB
random_21.txt AC 2 ms 3636 KiB
random_22.txt AC 2 ms 3644 KiB
sample_01.txt AC 1 ms 3536 KiB
sample_02.txt AC 1 ms 3584 KiB
sample_03.txt AC 1 ms 3572 KiB
Facebook Twitter Telegram Share

2025-06-16 (Mon)
12:30:46 +09:00

More…