pratiyush7

Service Engineers(GS Advanced)

Oct 25th, 2021
557
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Pratiyush Mishra
  2.  
  3. #include <bits/stdc++.h>
  4. #define ull unsigned long long int
  5. #define ll long long int
  6. #define LL_MAX 9223372036854775807
  7. #define pb push_back
  8. #define pf push_front
  9. #define mp make_pair
  10. #define popb pop_back
  11. #define vl vector<ll>
  12. #define pl pair<ll,ll>
  13. #define bs(v, x) binary_search(v.begin(), v.end(), x)
  14. #define mem1(a) memset(a, -1, sizeof(a))
  15. #define popf pop_front
  16. #define p0(x) cout << x << " "
  17. #define p1(x) cout << x << '\n'
  18. #define p2(x, y) cout << x << " " << y << '\n'
  19. #define p3(x, y, z) cout << x << " " << y << " " << z << '\n'
  20. #define printv(v)                   \
  21.   for (ll i = 0; i < v.size(); ++i) \
  22.     cout << v[i] << " ";            \
  23.   cout << '\n'
  24. #define pr1(x) cout << fixed << setprecision(15) << x << '\n'
  25. #define ordered_set tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update>
  26. // ordered_set s ; s.order_of_key(val)  no. of elements strictly less than val
  27. // s.find_by_order(i)  itertor to ith element (0 indexed)
  28. #define mod 1000000007
  29. #define mod1 998244353
  30. #define fio                         \
  31.   ios_base::sync_with_stdio(false); \
  32.   cin.tie(NULL)
  33. #define get(n) \
  34.   ll n;        \
  35.   cin >> n
  36. #define getvec(v, n)         \
  37.   vector<ll> v(n);           \
  38.   for (ll i = 0; i < n; i++) \
  39.     cin >> v[i];
  40. #define getstr(s) \
  41.   string s;       \
  42.   cin >> s
  43. #define all(x) x.begin(), x.end()
  44. #define countBits(x) __builtin_popcount(x)
  45. using namespace std;
  46.  
  47. int find(vector<int> &tree, int x)
  48. {
  49.     if (tree[x] == x)
  50.         return x;
  51.     return tree[x] = find(tree, tree[x]);
  52. }
  53.  
  54. void join(vector<int> &tree, int a, int b)
  55. {
  56.     int x = find(tree, a);
  57.     int y = find(tree, b);
  58.     if (x == y)
  59.         return;
  60.     tree[x] = y;
  61. }
  62.  
  63. void mainSolve()
  64. {
  65.     int n, m;
  66.     cin >> n >> m;
  67.     vector<vector<int>> v;
  68.     int ans = 0;
  69.     for (int i = 0; i < n; i++)
  70.     {
  71.         for (int j = 0; j < m; j++)
  72.         {
  73.             int x;
  74.             cin >> x;
  75.             if (x == 0)
  76.                 continue;
  77.             ans += x;
  78.             v.push_back({i, j, x});
  79.         }
  80.     }
  81.     vector<pair<int, pair<int, int>>> edges;
  82.     n = v.size();
  83.     vector<int> tree(n);
  84.     for (int i = 0; i < n; i++)
  85.         tree[i] = i;
  86.     for (int i = 0; i < n; i++)
  87.     {
  88.         for (int j = i + 1; j < n; j++)
  89.         {
  90.             vector<int> a = v[i];
  91.             vector<int> b = v[j];
  92.             int e = 2 * (abs(a[0] - b[0]) + abs(a[1] - b[1]));
  93.             edges.push_back({e, {i, j}});
  94.         }
  95.     }
  96.     sort(edges.begin(), edges.end());
  97.     for (auto it : edges)
  98.     {
  99.         int e = it.first;
  100.         int i = it.second.first;
  101.         int j = it.second.second;
  102.         int x = find(tree, i);
  103.         int y = find(tree, j);
  104.         if (x == y)
  105.             continue;
  106.         join(tree, x, y);
  107.         ans += e;
  108.     }
  109.     ans = (ans + 7) / 8;
  110.     p1(ans);
  111. }
  112.  
  113. int main()
  114. {
  115.     fio;
  116. #ifndef ONLINE_JUDGE
  117.     freopen("input.txt", "r", stdin);
  118.     freopen("output.txt", "w", stdout);
  119. #endif
  120.     get(t);
  121.     //ll t = 1;
  122.     while (t--)
  123.     {
  124.         mainSolve();
  125.     }
  126.     return 0;
  127. }
  128.  
RAW Paste Data