Advertisement
El_GEMMY

mines(topo sort)

Nov 18th, 2022
635
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.64 KB | None | 0 0
  1. // Those who cannot remember the past are
  2. // condemned to repeat it (use DP -_-)
  3. // - George Santayana
  4.  
  5. #include <bits/stdc++.h>
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8.  
  9. using namespace std;
  10. using namespace __gnu_pbds;
  11.  
  12. #define all(v) v.begin(), v.end()
  13. #define rall(v) v.rbegin(), v.rend()
  14. #define ll long long
  15. #define ull unsigned long long
  16. #define MOD 1000000007
  17. #define PI acos(-1)
  18. #define ceil(a, b) (((a) / (b)) + ((a) % (b) ? 1 : 0))
  19. #define imin INT_MIN
  20. #define imax INT_MAX
  21. #define llmax LLONG_MAX
  22. #define llmin LLONG_MIN
  23. #define inf 2000000000
  24. #define nl '\n'
  25. #define ppcnt __builtin_popcount
  26. #define ppcntll __builtin_popcountll
  27. #define clz __builtin_clz
  28. #define clzll __builtin_clzll
  29. #define ctz __builtin_ctz
  30. #define ctzll __builtin_ctzll
  31. #define modulo(a, b, mod) ((((a) % (mod)) + ((b) % (mod))) % (mod))
  32. #define cnte(v, x) count(all(v), (x))
  33. #define mine(v) min_element(all(v))
  34. #define maxe(v) max_element(all(v))
  35. #define updmin(a, b) a = min(a, b)
  36. #define updmax(a, b) a = max(a, b)
  37. #define findmod(x, m) x = ((x) % (m) + (m)) % m
  38. #define getmod(x, m) ((x) % (m) + (m)) % (m)
  39. #define debug(x) cout << "x: " << (x) << nl;
  40. #define debug2(x, y) cout << "x: " << (x) << " y: " << y << nl;
  41. #define ordered_set tree<pair<int, int>, null_type, less<>, rb_tree_tag, tree_order_statistics_int_update>
  42. #define ordered_map tree<int, int, less<>, rb_tree_tag, tree_order_statistics_int_update>
  43.  
  44. //vector<int> dx = {0, 0, 1, -1, 1, 1, -1, -1}, dy = {1, -1, 0, 0, 1, -1, 1, -1};
  45. //vector<int> dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
  46. //vector<int> dx = {2, 1, -1, -2, -2, -1, 1, 2}, dy = {1, 2, 2, 1, -1, -2, -2, -1};
  47.  
  48. template<typename T = int>
  49. istream &operator>>(istream &in, vector<pair<int, int>> &v) {
  50.     for (auto &[x, y]: v) in >> x >> y;
  51.     return in;
  52. }
  53.  
  54. template<typename T = int>
  55. istream &operator>>(istream &in, vector<T> &v) {
  56.     for (T &i: v) in >> i;
  57.     return in;
  58. }
  59.  
  60. template<typename T = int>
  61. ostream &operator<<(ostream &out, const vector<T> &v) {
  62.     for (const T &x: v)
  63.         out << x << ' ';
  64.     return out;
  65. }
  66.  
  67. template<typename T = pair<int, int>>
  68. ostream &operator<<(ostream &out, const vector<pair<int, int>> &v) {
  69.     for (auto &[x, y]: v) {
  70.         out << x << ' ' << y << nl;
  71.     }
  72.     return out;
  73. }
  74.  
  75. void Start_Crushing() {
  76.     ios_base::sync_with_stdio(false);
  77.     cin.tie(nullptr);
  78.     cout.tie(nullptr);
  79. #ifndef ONLINE_JUDGE
  80.     freopen("input.txt", "r", stdin);
  81.     freopen("output.txt", "w", stdout);
  82. #endif
  83. }
  84.  
  85. struct point {
  86.     int x, y, d;
  87.  
  88.     point(){
  89.         x = y = d = 0;
  90.     }
  91.     point(int x, int y, int d){
  92.         this -> x = x;
  93.         this -> y = y;
  94.         this -> d = d;
  95.     }
  96. };
  97.  
  98. bool good(point& a, point& b){
  99.     return abs(a.x - b.x) * 2 <= a.d and abs(a.y - b.y) * 2 <= a.d;
  100. }
  101.  
  102. void solve(){
  103.     int n; cin >> n;
  104.     vector<point> v(n);
  105.  
  106.     for(auto& [x, y, d] : v){
  107.         cin >> x >> y >> d;
  108.     }
  109.  
  110.     vector<vector<int>> adj(n + 5);
  111.  
  112.     for(int i = 1; i <= n; i++){
  113.         for(int j = 1; j <= n; j++){
  114.             if(i == j)
  115.                 continue;
  116.             if(good(v[i - 1], v[j - 1])){
  117.                 adj[i].emplace_back(j);
  118.             }
  119.         }
  120.     }
  121.  
  122.     vector<bool> vis(n + 5);
  123.     stack<int> topo;
  124.     function<void(int)> topological_sort = [&](int src){
  125.         vis[src] = true;
  126.  
  127.         for(auto& nxt : adj[src]){
  128.             if(not vis[nxt]){
  129.                 topological_sort(nxt);
  130.             }
  131.         }
  132.         topo.push(src);
  133.     };
  134.  
  135.     for(int i = 1; i <= n; i++){
  136.         if(not vis[i])
  137.             topological_sort(i);
  138.     }
  139.  
  140.     vis.assign(n + 5, false);
  141.     function<void(int)> dfs = [&](int src){
  142.         vis[src] = true;
  143.  
  144.         for(auto& nxt : adj[src]){
  145.             if(not vis[nxt]){
  146.                 dfs(nxt);
  147.             }
  148.         }
  149.     };
  150.  
  151.     int ans = 0;
  152.     while(not topo.empty()){
  153.         int curr = topo.top();
  154.         topo.pop();
  155.         if(not vis[curr]) {
  156.             dfs(curr);
  157.             ans++;
  158.         }
  159.     }
  160.     cout << ans;
  161. }
  162.  
  163. void set_file(string &file_name) {
  164.     freopen((file_name + ".in").c_str(), "r", stdin);
  165.     freopen((file_name + ".out").c_str(), "w", stdout);
  166. }
  167.  
  168. int main() {
  169.     Start_Crushing();
  170.  
  171. //    string file_name = "avia";
  172. //    set_file(file_name);
  173.     int t = 1;
  174.     /*Multiple test cases?*/ cin >> t;
  175.     while (t--) {
  176.         solve();
  177. //        if (!t)
  178. //            break;
  179.         cout << nl;
  180.     }
  181.  
  182. //    for(int tc = 1; tc <= t; tc++){
  183. ////        cout << "Case " << tc << ": ";
  184. //        solve();
  185. //        if(tc != t)
  186. //            cout << nl;
  187. //    }
  188.  
  189.     return 0;
  190. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement