Submission #66753813

Source Code Expand

Copy
#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;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
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#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;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(10,0);
	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];
				if(cycle){
					for(ll i=9;i>=0;i--){
						if(!(cycle&(1LL<<i)))continue;
						if(!XOR[i]){
							XOR[i]=cycle;
							break;
						}
						cycle^=XOR[i];
					}
				}
			}
		}
	}

	if(dist[n]==-1)M1;
	else{
		ll ans=dist[n];
		for(ll i=9;i>=0;i--){
			if(XOR[i]!=0 && (ans^XOR[i])<ans)ans^=XOR[i];
		}
		cout << ans << endl;
	}
}

Submission Info

Submission Time
Task D - XOR Shortest Walk
User ais_out
Language C++ 23 (gcc 12.2)
Score 0
Code Size 1780 Byte
Status WA
Exec Time 1 ms
Memory 3672 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 3488 KiB
hand_03.txt AC 1 ms 3580 KiB
hand_04.txt AC 1 ms 3568 KiB
hand_05.txt AC 1 ms 3564 KiB
hand_06.txt WA 1 ms 3632 KiB
hand_07.txt WA 1 ms 3460 KiB
hand_08.txt WA 1 ms 3636 KiB
random_01.txt AC 1 ms 3568 KiB
random_02.txt AC 1 ms 3596 KiB
random_03.txt AC 1 ms 3568 KiB
random_04.txt AC 1 ms 3668 KiB
random_05.txt AC 1 ms 3432 KiB
random_06.txt AC 1 ms 3576 KiB
random_07.txt AC 1 ms 3484 KiB
random_08.txt AC 1 ms 3584 KiB
random_09.txt AC 1 ms 3644 KiB
random_10.txt AC 1 ms 3624 KiB
random_11.txt AC 1 ms 3456 KiB
random_12.txt AC 1 ms 3672 KiB
random_13.txt AC 1 ms 3660 KiB
random_14.txt AC 1 ms 3480 KiB
random_15.txt AC 1 ms 3436 KiB
random_16.txt AC 1 ms 3492 KiB
random_17.txt AC 1 ms 3608 KiB
random_18.txt AC 1 ms 3524 KiB
random_19.txt AC 1 ms 3560 KiB
random_20.txt AC 1 ms 3560 KiB
random_21.txt AC 1 ms 3620 KiB
random_22.txt AC 1 ms 3628 KiB
sample_01.txt AC 1 ms 3564 KiB
sample_02.txt AC 1 ms 3480 KiB
sample_03.txt AC 1 ms 3608 KiB
Facebook Twitter Telegram Share

2025-08-22 (Fri)
00:00:40 +09:00

More…