Submission #68099575

---

Source Code Expand

#include <bits/stdc++.h>
#include <ctime>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define endl '\n'
#define cty cout<<"Yes"<<endl
#define ctn cout<<"No"<<endl
#define dbg(x) cout<<#x<<" : "<<x<<endl
#define int long long
const int mxn = 1e6+10;
double ST,ED;
inline int read(){
    int N = 0;char ch = getchar();
    while (ch>'9'||ch<'0') ch = getchar();
    while (ch>='0'&&ch<='9') N = N*10+ch-'0',ch = getchar();
    return N;
}
int n,m;
struct node{
	int u,v,w;
	bool vis = true;
}x[mxn];
int fa[mxn];
int find(int i){
	if(fa[i]==i) return i;
	return fa[i] = find(fa[i]);
}

void LonelyLunar_solve(){
	cin>>n>>m;
	ll ans = 0;
	for(int i = 1;i <= m; i++){
		cin>>x[i].u>>x[i].v>>x[i].w;
		x[i].vis = true;
	}
	for(int y = 30; y >= 0; y--){
		for(int i = 1;i <= n; i++) fa[i] = i;
		for(int i = 1;i <= m; i++){
			int tu = find(x[i].u),tv = find(x[i].v);
			if(tu==tv||!x[i].vis||(x[i].w>>y&1)) continue;
			fa[tu] = tv;
		}
		if(find(n)==find(1)){
			for(int i = 1;i <= m; i++) if(x[i].w>>y&1) x[i].vis = false;
		}
		else ans+=1<<y;
	}
	cout<<ans<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int _ = 1;
	ST = clock();
	//cin>>_;
	while(_--){
		LonelyLunar_solve();
	}
	ED = clock();
	cerr<<1000*(ED-ST)/CLOCKS_PER_SEC<<"ms\n";
	return 0;
}

Submission Info

Judge Result