(cache)Submission #66756452 - AtCoder Beginner Contest 410

Contest Duration: 2025-06-14(Sat) 21:00 - 2025-06-14(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #66756452

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ll N, M;
    cin >> N >> M;
    vector<vector<pair<ll,ll>>> edge(N);
    for (ll i=0; i<M; i++){
        ll A, B, W; cin >> A >> B >> W;
        A--; B--;
        edge[A].emplace_back(B, W);
    }
    vector<ll> dis(N, 0);
    vector<bool> vis(N, false);
    vector<ll> basis;
    function<void(ll)> dfs = [&](ll u){
        vis[u] = true;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

using ll = long long;

int main(){
    ll N, M;
    cin >> N >> M;

    vector<vector<pair<ll,ll>>> edge(N);
    for (ll i=0; i<M; i++){
        ll A, B, W; cin >> A >> B >> W;
        A--; B--;
        edge[A].emplace_back(B, W);
    }

    vector<ll> dis(N, 0);
    vector<bool> vis(N, false);
    vector<ll> basis;
    function<void(ll)> dfs = [&](ll u){
        vis[u] = true;
        for (auto [v, w] : edge[u]){
            if (!vis[v]){
                dis[v] = dis[u] ^ w;
                dfs(v);
            }
            else
            {
                ll cycle = dis[u] ^ w ^ dis[v];
                if(cycle) basis.push_back(cycle);
            }
        }
    };

    dfs(0);
    if (!vis[N-1]){
        cout << -1 << endl;
        return 0;
    }

    sort(basis.begin(), basis.end(), greater<ll>());
    vector<ll> xor_basis;
    for (ll v : basis){
        for(ll b : xor_basis) v = min(v, v^b);
        if(v) xor_basis.push_back(v);
    }
    sort(xor_basis.begin(), xor_basis.end(), greater<ll>());

    ll ans = dis[N-1];
    for(ll b : xor_basis) ans = min(ans, ans^b);
    cout << ans << endl;
}

Submission Info

Submission Time	2025-06-14 21:48:18
Task	D - XOR Shortest Walk
User	Belka
Language	C++ 20 (gcc 12.2)
Score	0
Code Size	1219 Byte
Status	WA
Exec Time	2 ms
Memory	3788 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

0 / 400

Status

× 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	3492 KiB
hand_02.txt	AC	1 ms	3640 KiB
hand_03.txt	AC	1 ms	3488 KiB
hand_04.txt	AC	1 ms	3540 KiB
hand_05.txt	AC	1 ms	3620 KiB
hand_06.txt	WA	1 ms	3488 KiB
hand_07.txt	WA	1 ms	3476 KiB
hand_08.txt	WA	1 ms	3432 KiB
random_01.txt	AC	1 ms	3624 KiB
random_02.txt	AC	1 ms	3780 KiB
random_03.txt	AC	1 ms	3544 KiB
random_04.txt	AC	1 ms	3488 KiB
random_05.txt	AC	1 ms	3480 KiB
random_06.txt	AC	1 ms	3532 KiB
random_07.txt	AC	1 ms	3404 KiB
random_08.txt	AC	1 ms	3572 KiB
random_09.txt	AC	1 ms	3500 KiB
random_10.txt	AC	1 ms	3628 KiB
random_11.txt	AC	1 ms	3428 KiB
random_12.txt	AC	1 ms	3644 KiB
random_13.txt	AC	1 ms	3640 KiB
random_14.txt	AC	1 ms	3524 KiB
random_15.txt	AC	1 ms	3692 KiB
random_16.txt	AC	1 ms	3568 KiB
random_17.txt	AC	2 ms	3788 KiB
random_18.txt	AC	2 ms	3648 KiB
random_19.txt	AC	1 ms	3704 KiB
random_20.txt	AC	1 ms	3616 KiB
random_21.txt	AC	2 ms	3612 KiB
random_22.txt	AC	1 ms	3608 KiB
sample_01.txt	AC	1 ms	3452 KiB
sample_02.txt	AC	1 ms	3544 KiB
sample_03.txt	AC	1 ms	3600 KiB