Submission #66748310

Source Code Expand

Copy
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using i128 = __int128_t;
#define LINF 9223372036854775807
#define rep(i, x, limit) for (ll i = (ll)x; i < (ll)limit; i++)
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p)
{
    os << "(" << p.first << "," << p.second << ")";
    return os;
}
template <typename T1, typename T2>
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using i128 = __int128_t;
#define LINF 9223372036854775807

#define rep(i, x, limit) for (ll i = (ll)x; i < (ll)limit; i++)

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p)
{
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p)
{
    is >> p.first >> p.second;
    return is;
}

template <typename T>
ostream &operator<<(ostream &os, const 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>
ostream &operator<<(ostream &os, const vector<vector<T>> &v)
{
    for (int i = 0; i < (int)v.size(); i++)
    {
        os << v[i] << endl;
    }
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v)
{
    for (int i = 0; i < (int)v.size(); i++)
    {
        os << "i = " << i << endl;
        os << v[i];
    }
    return os;
}

template <typename T>
istream &operator>>(istream &is, vector<T> &v)
{
    for (T &in : v)
        is >> in;
    return is;
}

template <typename T, typename S>
ostream &operator<<(ostream &os, const map<T, S> &mp)
{
    for (auto &[key, val] : mp)
    {
        os << key << ":" << val << " ";
    }
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const set<T> &st)
{
    auto itr = st.begin();
    for (int i = 0; i < (int)st.size(); i++)
    {
        os << *itr << (i + 1 != (int)st.size() ? " " : "");
        itr++;
    }
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &st)
{
    auto itr = st.begin();
    for (int i = 0; i < (int)st.size(); i++)
    {
        os << *itr << (i + 1 != (int)st.size() ? " " : "");
        itr++;
    }
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, queue<T> q)
{
    while (q.size())
    {
        os << q.front() << " ";
        q.pop();
    }
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, deque<T> q)
{
    while (q.size())
    {
        os << q.front() << " ";
        q.pop_front();
    }
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, stack<T> st)
{
    while (st.size())
    {
        os << st.top() << " ";
        st.pop();
    }
    return os;
}

template <class T, class Container, class Compare>
ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq)
{
    while (pq.size())
    {
        os << pq.top() << " ";
        pq.pop();
    }
    return os;
}

vector<ll> p;
vector<bool> visited;
vector<ll> c;
void dfs(ll v, ll par, vector<vector<pll>> &G, ll w)
{
    visited[v] = true;
    if (par == -1)
        p[v] = 0;
    else
        p[v] = p[par] ^ w;
    for (auto &[to, w] : G[v])
    {
        if (!visited[to])
        {
            dfs(to, v, G, w);
        }
        else
        {
            c.push_back(p[v] ^ p[to] ^ w);
        }
    }
}

int main()
{
    ll N, M;
    cin >> N >> M;
    vector<vector<pll>> G(N);
    rep(i, 0, M)
    {
        ll a, b, w;
        cin >> a >> b >> w;
        a--, b--;
        G[a].emplace_back(b, w);
        G[b].emplace_back(a, w);
    }
    p.assign(N, -1);
    visited.assign(N, false);
    dfs(0, -1, G, 0);
    if (p[N - 1] == -1)
    {
        cout << -1 << endl;
        return 0;
    }
    ll cur = p[N - 1];
    rep(i, 0, c.size())
    {
        if (cur ^ c[i] < cur)
        {
            cur ^= c[i];
        }
    }
    cout << cur << endl;
}

Submission Info

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

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:192:24: warning: suggest parentheses around comparison in operand of ‘^’ [-Wparentheses]
  192 |         if (cur ^ c[i] < cur)

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 3
AC × 25
WA × 8
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 3576 KiB
hand_02.txt AC 1 ms 3468 KiB
hand_03.txt WA 1 ms 3500 KiB
hand_04.txt AC 1 ms 3508 KiB
hand_05.txt AC 1 ms 3476 KiB
hand_06.txt AC 1 ms 3512 KiB
hand_07.txt WA 1 ms 3468 KiB
hand_08.txt WA 1 ms 3456 KiB
random_01.txt AC 1 ms 3472 KiB
random_02.txt AC 1 ms 3628 KiB
random_03.txt AC 1 ms 3472 KiB
random_04.txt AC 1 ms 3592 KiB
random_05.txt AC 1 ms 3480 KiB
random_06.txt AC 1 ms 3520 KiB
random_07.txt AC 1 ms 3496 KiB
random_08.txt AC 1 ms 3572 KiB
random_09.txt AC 1 ms 3472 KiB
random_10.txt AC 1 ms 3640 KiB
random_11.txt AC 1 ms 3472 KiB
random_12.txt AC 1 ms 3596 KiB
random_13.txt WA 1 ms 3580 KiB
random_14.txt WA 1 ms 3592 KiB
random_15.txt WA 1 ms 3604 KiB
random_16.txt AC 1 ms 3492 KiB
random_17.txt AC 2 ms 3852 KiB
random_18.txt AC 1 ms 3708 KiB
random_19.txt AC 2 ms 3768 KiB
random_20.txt AC 2 ms 3668 KiB
random_21.txt WA 2 ms 3496 KiB
random_22.txt WA 1 ms 3576 KiB
sample_01.txt AC 1 ms 3604 KiB
sample_02.txt AC 1 ms 3508 KiB
sample_03.txt AC 1 ms 3612 KiB
Facebook Twitter Telegram Share

2025-06-16 (Mon)
00:56:40 +09:00

More…