Snapper_001

Untitled

Sep 20th, 2024
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.14 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #include<ext/pb_ds/tree_policy.hpp>
  4. #pragma GCC optimize("O3", "unroll-loops")
  5. #pragma GCC target("avx2")
  6. using namespace __gnu_pbds;
  7. using namespace std;
  8. #define JAI_SHREE_RAAM ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  9. #define pb push_back
  10. #define all(x) (x).begin(),(x).end()
  11. #define ll long long
  12. #define ld long double
  13. #define eps 1e-9
  14. #define sz(a) (ll)(a).size()
  15. #define ppc __builtin_popcount
  16. #define ppcll __builtin_popcountll
  17. #define mem1(a) memset(a,-1,sizeof(a))
  18. #define mem0(a) memset(a,0,sizeof(a))
  19. #define endl "\n"
  20. #define lb lower_bound
  21. #define ub upper_bound
  22. #define iter vector<ll>::iterator
  23. #define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
  24. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  25. typedef unsigned long long ull;
  26. template<class T> using ordered_set = tree<T, null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
  27. template<class T> using ordered_multiset = tree<T, null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
  28. const ld PI = acos(-1.0);
  29. const int MOD = 1e9 +7;
  30. const ll INF = 1e18;
  31. // if(abs(a-b)<eps) --> if(a==b)
  32. // fixed << setprecision(n) -->printing decimal till n
  33. // hypot(a ,b) --> sqrt(a^2 + b^2)
  34.  
  35. void solve(){
  36. ll n ,r ,l;
  37. cin>>n>>r>>l;
  38.  
  39. //its kind of 2 sat
  40. // like each (x,y) has two value (true or false)
  41. // assume true: horizontol and flase for vertical
  42.  
  43. // for same row, if two of them overlap means they should not be true at same time
  44. // similar for row
  45.  
  46. // (1...l) for true
  47. // i+l for flase
  48.  
  49. // Then corresponding we make the graph and check strong connectivity
  50.  
  51. vector<pair<ll,ll>>temp;
  52. vector<ll>adj[2*l] , rev_adj[2*l];
  53. for(int i=0;i<l;i++){
  54. ll x , y;
  55. cin>>x>>y;
  56. x--;
  57. y--;
  58.  
  59. for(int j =0 ; j< temp.size();j++){
  60. if(temp[j].first == x){
  61. ll d = abs(temp[j].second - y);
  62. if(d >= 2*r+1) continue;
  63.  
  64. // it means (i , j) can not be true at same time
  65. // or for 2sat (i+l , j+l) can not be false at same time
  66.  
  67. adj[i].push_back(j+l);
  68. adj[j].push_back(i+l);
  69.  
  70. rev_adj[j+l].push_back(i);
  71. rev_adj[i+l].push_back(j);
  72.  
  73. }
  74.  
  75. if(temp[j].second == y){
  76. ll d = abs(temp[j].first - x);
  77. if(d >= 2*r+1) continue;
  78.  
  79. // it means (i , j) can not be false at same time (same for 2-sat)
  80.  
  81. adj[i+l].push_back(j);
  82. adj[j+l].push_back(i);
  83.  
  84. rev_adj[j].push_back(i+l);
  85. rev_adj[i].push_back(j+l);
  86. }
  87. }
  88. temp.push_back({x ,y});
  89. }
  90.  
  91. //Now check strong connectivity
  92. vector<ll>order;
  93. vector<ll>vis(2*l);
  94. function<void(ll)> dfs=[&](ll node){
  95. vis[node] = 1;
  96. for(auto it : adj[node]){
  97. if(!vis[it]) dfs(it);
  98. }
  99. order.push_back(node);
  100. };
  101. for (int i = 0; i < 2*l; i++){
  102. if (!vis[i]){
  103. dfs(i);
  104. }
  105. }
  106.  
  107. reverse(all(order));
  108. vis.assign(2*l, 0);
  109. vector<ll>component;
  110. function<void(ll)> dfs2=[&](ll node){
  111. vis[node] = 1;
  112. component.push_back(node);
  113. for(auto it : rev_adj[node]){
  114. if(!vis[it]) dfs2(it);
  115. }
  116. };
  117. for(auto it : order){
  118. if(!vis[it]){
  119. dfs2(it);
  120. //process the component
  121. unordered_map<ll,ll>mp;
  122. for(auto it : component){
  123. mp[it] = 1;
  124. }
  125. for(auto it : component){
  126. if(it < l && mp.count(it + l)){
  127. cout << "NO" <<endl;
  128. return;
  129. }
  130. }
  131. component.clear();
  132. }
  133. }
  134.  
  135. cout << "YES" << endl;
  136.  
  137. }
  138.  
  139. int main(){
  140. JAI_SHREE_RAAM
  141.  
  142. ll t =1;
  143. // cin>>t;
  144. for(int i=1;i<=t;i++){
  145. // cout<<"Case #"<<i<<": ";
  146. solve();
  147. }
  148. return 0;
  149. }
Advertisement
Add Comment
Please, Sign In to add comment