(cache)Submission #66734729 - 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 #66734729

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;
vector<int> p;              
vector<int> x;              
vector<vector<int>> b;     
int f(int i) {
    if (p[i] == i) return i;
    int r = f(p[i]);
    x[i] ^= x[p[i]];
    p[i] = r;
    return r;
}
void a(vector<int>& bs, int v) {
    for (int bv : bs) {
        v = min(v, v ^ bv);
    }
    if (v > 0) bs.push_back(v);
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

vector<int> p;              
vector<int> x;              
vector<vector<int>> b;     

int f(int i) {
    if (p[i] == i) return i;
    int r = f(p[i]);
    x[i] ^= x[p[i]];
    p[i] = r;
    return r;
}

void a(vector<int>& bs, int v) {
    for (int bv : bs) {
        v = min(v, v ^ bv);
    }
    if (v > 0) bs.push_back(v);
}

void u(int i, int j, int w) {
    int ri = f(i), rj = f(j);
    if (ri != rj) {
        p[rj] = ri;
        x[rj] = x[j] ^ w ^ x[i];
        for (int v : b[rj]) a(b[ri], v);
        b[rj].clear();
    } else {
        int c = w ^ x[i] ^ x[j];
        a(b[ri], c);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; cin >> n >> m;

    p.resize(n + 1);
    iota(p.begin(), p.end(), 0);
    x.assign(n + 1, 0);
    b.assign(n + 1, vector<int>());

    for (int _ = 0; _ < m; _++) {
        int i, j, w; cin >> i >> j >> w;
        u(i, j, w);
    }

    if (f(1) != f(n)) {
        cout << -1 << '\n';
    } else {
        int r = f(1);
        int px = x[1] ^ x[n];
        for (int v : b[r]) px = min(px, px ^ v);
        cout << px << '\n';
    }

    return 0;
}

Submission Info

Submission Time	2025-06-14 21:14:35
Task	D - XOR Shortest Walk
User	aiko_cse4
Language	C++ 20 (gcc 12.2)
Score	0
Code Size	1245 Byte
Status	WA
Exec Time	1 ms
Memory	3640 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

0 / 400

Status

× 3

AC	× 28
WA	× 5

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	3532 KiB
hand_02.txt	AC	1 ms	3476 KiB
hand_03.txt	WA	1 ms	3456 KiB
hand_04.txt	AC	1 ms	3476 KiB
hand_05.txt	WA	1 ms	3412 KiB
hand_06.txt	WA	1 ms	3480 KiB
hand_07.txt	WA	1 ms	3468 KiB
hand_08.txt	WA	1 ms	3528 KiB
random_01.txt	AC	1 ms	3384 KiB
random_02.txt	AC	1 ms	3408 KiB
random_03.txt	AC	1 ms	3476 KiB
random_04.txt	AC	1 ms	3344 KiB
random_05.txt	AC	1 ms	3612 KiB
random_06.txt	AC	1 ms	3620 KiB
random_07.txt	AC	1 ms	3412 KiB
random_08.txt	AC	1 ms	3408 KiB
random_09.txt	AC	1 ms	3532 KiB
random_10.txt	AC	1 ms	3496 KiB
random_11.txt	AC	1 ms	3416 KiB
random_12.txt	AC	1 ms	3496 KiB
random_13.txt	AC	1 ms	3476 KiB
random_14.txt	AC	1 ms	3496 KiB
random_15.txt	AC	1 ms	3484 KiB
random_16.txt	AC	1 ms	3488 KiB
random_17.txt	AC	1 ms	3420 KiB
random_18.txt	AC	1 ms	3616 KiB
random_19.txt	AC	1 ms	3424 KiB
random_20.txt	AC	1 ms	3520 KiB
random_21.txt	AC	1 ms	3492 KiB
random_22.txt	AC	1 ms	3640 KiB
sample_01.txt	AC	1 ms	3460 KiB
sample_02.txt	AC	1 ms	3484 KiB
sample_03.txt	AC	1 ms	3516 KiB