#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, ans;
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, 31)
{
if (guys[i].none()) continue;
ord.PB(i);
val[i] = (1 << i);
}
sort(ALL(ord), [&](int a, int b)
{
return cmp(guys[a], guys[b]);
});
//just find which # is smaller.
vi rem;
int mask = 0;
FOR(i, 0, SZ(ord))
{
FORD(j, SZ(rem), 0)
{
if (cmp(guys[ord[i]] ^ guys[rem[j]], guys[ord[i]]))
{
guys[ord[i]] ^= guys[rem[j]];
val[rem[j]] ^= val[ord[i]];
}
}
if (guys[ord[i]].none()) continue;
ans++;
// cerr << "PUSH " << ord[i] << ' ' << endl;
FOR(j, 0, SZ(rem) + 1)
{
if (j == SZ(rem) || cmp(guys[ord[i]], guys[rem[j]]))
{
rem.insert(rem.begin() + j, ord[i]);
break;
}
}
//you have this bitset.
}
// for (int x : ord)
// {
// cerr << x << ' ' << val[x] << endl;
// FOR(j, 0, M)
// {
// cerr << guys[x][j];
// }
// cerr << endl;
// }
cout << ans << '\n';
FOR(i, 0, 31)
{
// cerr << guys[i].to_ullong() << ' ';
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:122:9: warning: unused variable 'mask' [-Wunused-variable]
122 | int mask = 0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
6508 KB |
Output is correct |
| 2 |
Correct |
40 ms |
7020 KB |
Output is correct |
| 3 |
Correct |
9 ms |
3840 KB |
Output is correct |
| 4 |
Correct |
11 ms |
3820 KB |
Output is correct |
| 5 |
Correct |
81 ms |
10752 KB |
Output is correct |
| 6 |
Correct |
86 ms |
10092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
4716 KB |
Output is correct |
| 2 |
Correct |
16 ms |
4716 KB |
Output is correct |
| 3 |
Correct |
21 ms |
5356 KB |
Output is correct |
| 4 |
Correct |
24 ms |
5740 KB |
Output is correct |
| 5 |
Correct |
77 ms |
9708 KB |
Output is correct |
| 6 |
Correct |
40 ms |
7148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
68 ms |
9708 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2924 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
9580 KB |
Output is correct |
| 2 |
Correct |
118 ms |
12140 KB |
Output is correct |
| 3 |
Correct |
5 ms |
3180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
8300 KB |
Output is correct |
| 2 |
Correct |
73 ms |
9964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
9708 KB |
Output is correct |
| 2 |
Correct |
42 ms |
7532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
9836 KB |
Output is correct |
| 2 |
Correct |
108 ms |
11344 KB |
Output is correct |
| 3 |
Correct |
70 ms |
10092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
122 ms |
12268 KB |
Output is correct |
| 2 |
Correct |
147 ms |
14828 KB |
Output is correct |
| 3 |
Correct |
143 ms |
14700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
5484 KB |
Output is correct |
| 2 |
Correct |
34 ms |
6636 KB |
Output is correct |
| 3 |
Correct |
95 ms |
11500 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
10604 KB |
Output is correct |
| 2 |
Correct |
52 ms |
8428 KB |
Output is correct |
| 3 |
Correct |
122 ms |
14188 KB |
Output is correct |
