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

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;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
using vl = vc<ll>;
using vvl = vc<vc<ll>>;
using vul = vc<ull>;
using vs = vc<string>;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep1(i,n) for(ll i=1;i<=(n);i++)
#define Rep(i,n) for(ll i=n-1;i>=0;i--)
//#define rep(i,n) for(ull i=0;i<(n);i++)
#define nall(x) x.begin(),x.end()
#define pb push_back
#define pob pop_back
#define YES cout<<"Yes"<<endl
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
using vl = vc<ll>;
using vvl = vc<vc<ll>>;
using vul = vc<ull>;
using vs = vc<string>;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep1(i,n) for(ll i=1;i<=(n);i++)
#define Rep(i,n) for(ll i=n-1;i>=0;i--)
//#define rep(i,n) for(ull i=0;i<(n);i++)
#define nall(x) x.begin(),x.end()
#define pb push_back
#define pob pop_back
#define YES cout<<"Yes"<<endl
#define NO cout<<"No"<<endl
#define YN {cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define M1 cout<<"-1"<<endl
const long long INF = (1LL<<62)-(1LL<<31)-1;
#define denl endl
#define edln endl
#define ednl endl
//vl dx = {1,-1,0,0};vl dy = {0,0,1,-1};
//vl dx={0,0,1,1,1,-1,-1,-1};vl dy={1,-1,0,1,-1,0,1,-1};
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	ll n,m;
	cin >> n >> m;
	vv<pair<ll,ll>> g(n+1);
	rep(i,m){
		ll a,b,w;
		cin >> a >> b >> w;
		g[a].pb({b,w});
	}
	vl dist(n+1,-1);
	vl XOR;
	queue<ll> q;
	dist[1]=0;
	q.push(1);
	while(!q.empty()){
		ll from=q.front();
		q.pop();
		for(auto [to,w]:g[from]){
			ll x=dist[from]^w;
			if(dist[to]==-1){
				dist[to]=x;
				q.push(to);
			}
			else{
				ll cycle=x^dist[to];
				for(auto p:XOR)cycle=min(cycle,cycle^p);
				if(cycle)XOR.pb(cycle);
			}
		}
	}

	if(dist[n]==-1)M1;
	else{
		ll ans=dist[n];
		for(auto p:XOR)ans=min(ans,ans^p);
		cout << ans << endl;
	}
}

Submission Info

Submission Time	2025-06-14 21:28:02
Task	D - XOR Shortest Walk
User	ais_out
Language	C++ 23 (gcc 12.2)
Score	0
Code Size	1624 Byte
Status	WA
Exec Time	1 ms
Memory	3740 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	3472 KiB
hand_02.txt	AC	1 ms	3544 KiB
hand_03.txt	AC	1 ms	3556 KiB
hand_04.txt	AC	1 ms	3680 KiB
hand_05.txt	AC	1 ms	3600 KiB
hand_06.txt	WA	1 ms	3520 KiB
hand_07.txt	WA	1 ms	3532 KiB
hand_08.txt	WA	1 ms	3476 KiB
random_01.txt	AC	1 ms	3460 KiB
random_02.txt	AC	1 ms	3480 KiB
random_03.txt	AC	1 ms	3544 KiB
random_04.txt	AC	1 ms	3556 KiB
random_05.txt	AC	1 ms	3468 KiB
random_06.txt	AC	1 ms	3624 KiB
random_07.txt	AC	1 ms	3520 KiB
random_08.txt	AC	1 ms	3696 KiB
random_09.txt	AC	1 ms	3536 KiB
random_10.txt	AC	1 ms	3492 KiB
random_11.txt	AC	1 ms	3536 KiB
random_12.txt	AC	1 ms	3504 KiB
random_13.txt	AC	1 ms	3564 KiB
random_14.txt	AC	1 ms	3688 KiB
random_15.txt	AC	1 ms	3480 KiB
random_16.txt	AC	1 ms	3700 KiB
random_17.txt	AC	1 ms	3668 KiB
random_18.txt	AC	1 ms	3464 KiB
random_19.txt	AC	1 ms	3540 KiB
random_20.txt	AC	1 ms	3740 KiB
random_21.txt	AC	1 ms	3608 KiB
random_22.txt	AC	1 ms	3588 KiB
sample_01.txt	AC	1 ms	3400 KiB
sample_02.txt	AC	1 ms	3588 KiB
sample_03.txt	AC	1 ms	3584 KiB