fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8.  
  9. struct Node {
  10.     int ch[2];
  11.     int cnt;
  12. };
  13.  
  14. const int MAX_N = 200005;
  15. const int MAX_NODES = MAX_N * 32;
  16. Node trie[MAX_NODES];
  17. int node_count = 0;
  18.  
  19. void reset_trie() {
  20.     for (int i = 0; i <= node_count; ++i) {
  21.         trie[i].ch[0] = trie[i].ch[1] = 0;
  22.         trie[i].cnt = 0;
  23.     }
  24.     node_count = 0;
  25. }
  26.  
  27. int new_node() {
  28.     node_count++;
  29.     trie[node_count].ch[0] = trie[node_count].ch[1] = 0;
  30.     trie[node_count].cnt = 0;
  31.     return node_count;
  32. }
  33.  
  34. void insert_trie(ll val) {
  35.     int curr = 0;
  36.     trie[curr].cnt++;
  37.     for (int i = 29; i >= 0; --i) {
  38.         int bit = (val >> i) & 1;
  39.         if (!trie[curr].ch[bit]) trie[curr].ch[bit] = new_node();
  40.         curr = trie[curr].ch[bit];
  41.         trie[curr].cnt++;
  42.     }
  43. }
  44.  
  45. ll query_trie(ll val, ll k) {
  46.     int curr = 0;
  47.     ll res = 0;
  48.     for (int i = 29; i >= 0; --i) {
  49.         if (curr == -1) break;
  50.         int v_bit = (val >> i) & 1;
  51.         int k_bit = (k >> i) & 1;
  52.         if (k_bit == 1) {
  53.             if (trie[curr].ch[v_bit]) res += trie[trie[curr].ch[v_bit]].cnt;
  54.             curr = trie[curr].ch[1 - v_bit] ? trie[curr].ch[1 - v_bit] : -1;
  55.         } else {
  56.             curr = trie[curr].ch[v_bit] ? trie[curr].ch[v_bit] : -1;
  57.         }
  58.     }
  59.     if (curr != -1) res += trie[curr].cnt;
  60.     return res;
  61. }
  62.  
  63. ll basis[31];
  64. void insert_basis(ll x) {
  65.     for (int i = 29; i >= 0; --i) {
  66.         if (!(x >> i & 1)) continue;
  67.         if (!basis[i]) {
  68.             basis[i] = x;
  69.             return;
  70.         }
  71.         x ^= basis[i];
  72.     }
  73. }
  74.  
  75. ll minimize(ll x) {
  76.     for (int i = 29; i >= 0; --i) {
  77.         if ((x >> i & 1) && basis[i]) x ^= basis[i];
  78.     }
  79.     return x;
  80. }
  81.  
  82. vector<pair<int, ll>> adj[MAX_N];
  83. ll D[MAX_N];
  84. bool vis[MAX_N];
  85.  
  86. void dfs(int u, ll cur_xor) {
  87.     vis[u] = true;
  88.     D[u] = cur_xor;
  89.     for (auto& edge : adj[u]) {
  90.         int v = edge.first;
  91.         ll w = edge.second;
  92.         if (!vis[v]) {
  93.             dfs(v, cur_xor ^ w);
  94.         } else {
  95.             insert_basis(D[u] ^ D[v] ^ w);
  96.         }
  97.     }
  98. }
  99.  
  100. void solve() {
  101.     int n, m;
  102.     ll k;
  103.     if (!(cin >> n >> m >> k)) return;
  104.  
  105.     for (int i = 1; i <= n; ++i) {
  106.         adj[i].clear();
  107.         vis[i] = false;
  108.         D[i] = 0;
  109.     }
  110.     for (int i = 0; i < 31; ++i) basis[i] = 0;
  111.     reset_trie();
  112.  
  113.     for (int i = 0; i < m; ++i) {
  114.         int u, v;
  115.         ll w;
  116.         cin >> u >> v >> w;
  117.         adj[u].push_back({v, w});
  118.         adj[v].push_back({u, w});
  119.     }
  120.  
  121.     dfs(1, 0);
  122.  
  123.     ll ans = 0;
  124.     for (int i = 1; i <= n; ++i) {
  125.         ll val = minimize(D[i]);
  126.         ans += query_trie(val, k);
  127.         insert_trie(val);
  128.     }
  129.     cout << ans << "\n";
  130. }
  131.  
  132. int main() {
  133.     ios::sync_with_stdio(false);
  134.     cin.tie(nullptr);
  135.     int t;
  136.     cin >> t;
  137.     while (t--) {
  138.         solve();
  139.     }
  140.     return 0;
  141. }
  142.  
Success #stdin #stdout 0.01s 9588KB
comments (?)
stdin
copy 
3
4 4 2
3 4 3
1 3 4
1 2 3
2 3 2
5 7 14032
1 2 24681
3 5 25665
1 5 14154
2 3 23215
1 3 21259
4 5 24874
3 4 26495
8 10 109312507
6 8 793188457
7 8 501937135
1 2 954888411
2 7 109497327
1 6 791995625
2 6 665857693
1 3 101233808
1 7 114788578
4 6 953503358
5 8 624700613
stdout
copy 
4
9
22
https://ideone.com/hLzg6b
language:
C++14 (gcc 8.3)
created:
2 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!