#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;
// template<class T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef pair<pii, int> ppi;
const int MAXN = 100013;
int N, M;
vector<ppi> edge[MAXN];
bitset<MAXN> seen;
int parent[MAXN], val[MAXN], depth[MAXN];
bitset<MAXN> guys[32];
vi ord;
void dfs(int u)
{
seen[u] = true;
for (auto e : edge[u])
{
int v = e.se;
if (seen[v]) continue;
parent[v] = u;
depth[v] = depth[u] + 1;
val[v] = (val[u] ^ e.fi.fi);
dfs(v);
}
}
bool cmp(bitset<MAXN> a, bitset<MAXN> b) //is a < b.
{
FORD(i, M, 0)
{
if (a[i] ^ b[i])
{
return (b[i]);
}
}
return false;
}
int32_t main()
{
cout << fixed << setprecision(12);
cerr << fixed << setprecision(4);
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> N >> M;
FOR(i, 0, M)
{
int u, v, p;
cin >> u >> v >> p;
u--; v--;
edge[u].PB({{p, i}, v});
edge[v].PB({{p, i}, u});
}
parent[0] = N;
dfs(0);
FOR(u, 0, N)
{
for (auto e : edge[u])
{
int v = e.se;
if (v == parent[u] || depth[v] >= depth[u]) continue;
int c = (val[u] ^ val[v] ^ e.fi.fi);
FORD(j, 31, 0)
{
if (c & (1 << j))
{
guys[j][e.fi.se] = true;
// cerr << j << ' ' << e.fi.se << endl;
}
}
}
}
FOR(i, 0, 32)
{
if (guys[i].none()) continue;
ord.PB(i);
}
sort(ALL(ord), [&](int a, int b)
{
return cmp(guys[a], guys[b]);
});
int mask = 0;
FOR(i, 0, SZ(ord))
{
val[ord[i]] = (1 << ord[i]);
FORD(j, i, 0)
{
if (cmp(guys[ord[i]] ^ guys[ord[j]], guys[ord[i]]))
{
guys[ord[i]] ^= guys[ord[j]];
val[ord[j]] ^= val[ord[i]];
}
}
//you have this bitset.
}
// for (int x : ord)
// {
// cerr << x << ' ' << val[x] << endl;
// FOR(j, 0, M)
// {
// cerr << guys[x][j];
// }
// cerr << endl;
// }
int ans = 0;
FOR(i, 0, 32) if (guys[i].any()) ans++;
cout << ans << '\n';
FOR(i, 0, 32)
{
if (guys[i].none()) continue;
cout << val[i] << ' ' << guys[i].count();
FOR(j, 0, M)
{
if (guys[i][j])
{
cout << ' ' << j + 1;
}
}
cout << '\n';
}
return 0;
// FOR(i, 0, 32)
// {
// if (val[i] == 0) continue;
// cout << val[i] << ' ' << out[i].count();
// FOR(j, 0, M)
// {
// if (out[i][j])
// {
// cout << ' ' << j + 1;
// }
// }
// cout << '\n';
// }
//now we decide how to group them up. you have a bunch of bases.
// cout << ans << '\n';
// FOR(i, 0, ans)
// {
// cout << res[i] << ' ' << SZ(guys[group[i]]);
// for (int x : guys[group[i]])
// {
// cout << ' ' << x + 1;
// }
// cout << '\n';
// }
return 0;
}
Compilation message
parkticni.cpp: In function 'int32_t main()':
parkticni.cpp:119:9: warning: unused variable 'mask' [-Wunused-variable]
119 | int mask = 0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
6272 KB |
Output is correct |
| 2 |
Correct |
42 ms |
6636 KB |
Output is correct |
| 3 |
Correct |
9 ms |
3584 KB |
Output is correct |
| 4 |
Correct |
8 ms |
3564 KB |
Output is correct |
| 5 |
Correct |
78 ms |
10368 KB |
Output is correct |
| 6 |
Correct |
91 ms |
9708 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
4332 KB |
Output is correct |
| 2 |
Correct |
15 ms |
4332 KB |
Output is correct |
| 3 |
Correct |
19 ms |
4992 KB |
Output is correct |
| 4 |
Correct |
23 ms |
5356 KB |
Output is correct |
| 5 |
Correct |
80 ms |
9324 KB |
Output is correct |
| 6 |
Correct |
48 ms |
6892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
7020 KB |
Too many operations |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
85 ms |
9216 KB |
Output is correct |
| 2 |
Incorrect |
138 ms |
13936 KB |
Too many operations |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
80 ms |
8300 KB |
Too many operations |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
10348 KB |
Too many operations |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
9708 KB |
Too many operations |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
129 ms |
12268 KB |
Too many operations |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
5228 KB |
Too many operations |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
102 ms |
10348 KB |
Too many operations |
| 2 |
Halted |
0 ms |
0 KB |
- |
