#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];
vi guys[32]; //set of edge ids that need to be xored by 2^i.
int res[32], group[32];
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);
}
}
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].PB(e.fi.se);
// cerr << j << ' ' << e.fi.se << endl;
}
}
}
}
int done = 0;
FOR(i, 0, 31)
{
if (guys[i].empty()) continue;
if (done & (1 << i)) continue;
done |= (1 << i);
res[ans] = (1 << i);
group[ans] = i;
FOR(j, i + 1, 31)
{
if (guys[i] == guys[j])
{
res[ans] |= (1 << j);
done |= (1 << j);
}
}
ans++;
}
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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
7788 KB |
Output is correct |
2 |
Correct |
42 ms |
7660 KB |
Output is correct |
3 |
Correct |
9 ms |
3948 KB |
Output is correct |
4 |
Correct |
9 ms |
3820 KB |
Output is correct |
5 |
Correct |
87 ms |
12396 KB |
Output is correct |
6 |
Correct |
102 ms |
11500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
4972 KB |
Output is correct |
2 |
Correct |
16 ms |
4844 KB |
Output is correct |
3 |
Correct |
21 ms |
5484 KB |
Output is correct |
4 |
Correct |
25 ms |
5996 KB |
Output is correct |
5 |
Correct |
80 ms |
12032 KB |
Output is correct |
6 |
Correct |
39 ms |
8556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
47 ms |
8300 KB |
Too many operations |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
93 ms |
11628 KB |
Too many operations |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
64 ms |
9964 KB |
Too many operations |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
99 ms |
13888 KB |
Too many operations |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
88 ms |
11756 KB |
Too many operations |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
140 ms |
16108 KB |
Too many operations |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
23 ms |
5612 KB |
Too many operations |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
102 ms |
13036 KB |
Too many operations |
2 |
Halted |
0 ms |
0 KB |
- |