#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, d[N], cl[N];
vector < pair < pair < int, int >, int > > g[N];
vector < pair < int, int > > e;
void dfs(int v, int pr = -1){
cl[v] = 1;
for(auto it : g[v]){
int to = it.first.first, len = it.first.second;
if(to != pr){
if(!cl[to]){
d[to] = (d[v] ^ len);
dfs(to, v);
}
else if(cl[to] == 1){
e.push_back(make_pair((d[v] ^ len ^ d[to]), it.second));
}
}
}
cl[v] = 2;
}
vector < int > bas;
map < int, vector < int > > ans;
inline void add(int x){
for(auto it : bas){
x = min(x, (x ^ it));
}
if(!x){
return;
}
for(auto &it : bas){
it = min(it, (it ^ x));
}
bas.push_back(x);
sort(bas.rbegin(), bas.rend());
}
inline void upd(int x, int y){
int cur = 0;
for(auto it : bas){
if((x ^ it) < x){
cur ^= it;
x ^= it;
}
}
ans[cur].push_back(y);
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++){
int x, y, z;
cin >> x >> y >> z;
g[x].push_back(make_pair(make_pair(y, z), i));
g[y].push_back(make_pair(make_pair(x, z), i));
}
dfs(1);
for(auto it : e){
if(it.first){
add(it.first);
}
}
for(auto it : e){
if(it.first){
upd(it.first, it.second);
}
}
cout << (int)ans.size() << "\n";
for(auto it : ans){
cout << it.first << " ";
for(auto x : it.second){
cout << x << " ";
}
cout << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
31 ms |
6264 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
15 ms |
4344 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
40 ms |
7288 KB |
Integer 48848 violates the range [1, 48785] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
68 ms |
8824 KB |
Integer 267576 violates the range [1, 90970] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
45 ms |
7416 KB |
Integer 84064 violates the range [1, 66382] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
69 ms |
8300 KB |
Integer 84483 violates the range [1, 73386] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
82 ms |
9248 KB |
Integer 232999 violates the range [1, 90440] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
104 ms |
12532 KB |
Integer 103542 violates the range [1, 98970] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
23 ms |
4648 KB |
Integer 2789814 violates the range [1, 31757] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
97 ms |
9948 KB |
Integer 402840 violates the range [1, 96069] |
2 |
Halted |
0 ms |
0 KB |
- |