№ |
Отправитель |
Задача |
Язык |
Вердикт |
Время |
Память |
Отослано |
Протест. |
|
211759207 |
Дорешивание:
Sangamer |
1624G
- 20
|
C++17 (GCC 7-32)
|
Полное решение
|
311 мс
|
9584 КБ
|
2023-07-01 21:58:39 |
2023-07-01 21:58:39 |
|
#include<bits/stdc++.h>
using namespace std;
struct DSU{
vector< int > el;
DSU(int n){
el=vector<int>(n,-1);
}
int find(int x){
if(el[x]<0){
return x;
}
return el[x]=find(el[x]);
}
int siz(int x){
return -el[find(x)];
}
bool unite(int a,int b){
int p1=find(a);
int p2=find(b);
if(p1==p2){
return false;
}
if(el[p1]>el[p2]){
swap(p1,p2);
}
el[p1]+=el[p2];
el[p2]=p1;
return true;
}
};
void tc(){
int n , m;
cin >> n >> m;
vector<vector<int>>gra(m,vector<int>(3));
for(int i = 0; i < m; i++){
int a , b , w;
cin >> a >> b >> w;
gra[i] = {--a , --b , w};
}
int ans = 0;
vector<int> av(m , 1);
for(int j = 31; j >= 0; j--)
{
int x = 1<<j;
int cnt = 0;
DSU dsu(n);
vector<int> taken(m , 0);
for(int i = 0; i < m; i++)
{
if( av[i] && !(x&gra[i][2]))
{
taken[i]=1;
if(dsu.unite(gra[i][0] , gra[i][1]))
{
cnt++;
}
}
}
if(cnt < n-1)
{
ans = ans|(x);
}
else
{
for(int i = 0; i < m; i++)
{
av[i] = taken[i];
}
}
}
cout << ans << "\n";
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tt,q=1;
cin>>tt;
while(tt--)
{
tc();
}
return 0;
}
Время: ? ms, память: ? КБ