/**
* code generated by JHelper
* More info: https://github.com/AlexeyDmitriev/JHelper
* @author
*/
#include <bits/stdc++.h>
using namespace std;
#define long long long
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 1e5+1;
struct edge {
int v, w, i;
edge(int v, int w, int i): v(v), w(w), i(i) {}
};
class TaskE {
int n, m;
vector<edge> g[N];
vector<pair<int,int> > vals;
int basis[32];
int f[N];
bool mark[N];
void dfs(int u, int par) {
mark[u] = true;
for(auto e: g[u]) {
if(e.v == par) continue;
if(mark[e.v]) {
// cerr << u << ' ' << e.v << ' ' << (f[u] ^ f[e.v] ^ e.w) << endl;
vals.emplace_back(f[u] ^ f[e.v] ^ e.w, e.i);
} else {
f[e.v] = f[u] ^ e.w;
dfs(e.v, u);
}
}
}
public:
void solve(istream &cin, ostream &cout) {
cin >> n >> m;
for(int i = 0, u, v, w; i < m; i++) {
cin >> u >> v >> w;
g[u].emplace_back(v, w, i + 1);
g[v].emplace_back(u, w, i + 1);
}
dfs(1, 0);
vector<vector<int> > ans;
for(int j = 31; j >= 0; j--) {
vector<int> tmp;
for(int i = 0; i < vals.size(); i++) if(vals[i].first >> j & 1) {
// cerr << (1 << j) << ' ' << vals[i].first << ' ' << vals[i].second << endl;
if(!basis[j]) {
basis[j] = vals[i].first;
tmp.push_back(vals[i].second);
} else {
if(vals[i].first > (vals[i].first ^ basis[j])) {
tmp.push_back(vals[i].second);
}
}
vals[i].first ^= basis[j];
}
if(tmp.empty()) continue;
tmp.insert(tmp.begin(), tmp.size());
tmp.insert(tmp.begin(), basis[j]);
ans.push_back(tmp);
}
cout << ans.size() << '\n';
for(vector<int> v: ans) {
for(int x: v) cout << x << ' ';
cout << '\n';
}
}
};
class Solver {
public:
void solve(std::istream& in, std::ostream& out) {
TaskE *obj = new TaskE();
obj->solve(in, out);
delete obj;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solver solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}
Compilation message
parkticni.cpp: In member function 'void TaskE::solve(std::istream&, std::ostream&)':
parkticni.cpp:56:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < vals.size(); i++) if(vals[i].first >> j & 1) {
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
6516 KB |
There is a simple cycle which is not good |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
5116 KB |
There is a simple cycle which is not good |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
8104 KB |
There is a simple cycle which is not good |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
103 ms |
8736 KB |
There is a simple cycle which is not good |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
8052 KB |
There is a simple cycle which is not good |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
132 ms |
13628 KB |
There is a simple cycle which is not good |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
142 ms |
9472 KB |
There is a simple cycle which is not good |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
169 ms |
15600 KB |
There is a simple cycle which is not good |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
5084 KB |
There is a simple cycle which is not good |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
116 ms |
10488 KB |
There is a simple cycle which is not good |
| 2 |
Halted |
0 ms |
0 KB |
- |
