Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #include<ext/pb_ds/assoc_container.hpp>
- #include<ext/pb_ds/tree_policy.hpp>
- #pragma GCC optimize("O3", "unroll-loops")
- #pragma GCC target("avx2")
- using namespace __gnu_pbds;
- using namespace std;
- #define JAI_SHREE_RAAM ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
- #define pb push_back
- #define all(x) (x).begin(),(x).end()
- #define ll long long
- #define ld long double
- #define eps 1e-9
- #define sz(a) (ll)(a).size()
- #define ppc __builtin_popcount
- #define ppcll __builtin_popcountll
- #define mem1(a) memset(a,-1,sizeof(a))
- #define mem0(a) memset(a,0,sizeof(a))
- #define endl "\n"
- #define lb lower_bound
- #define ub upper_bound
- #define iter vector<ll>::iterator
- #define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- typedef unsigned long long ull;
- template<class T> using ordered_set = tree<T, null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
- template<class T> using ordered_multiset = tree<T, null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
- const ld PI = acos(-1.0);
- const int MOD = 1e9 +7;
- const ll INF = 1e18;
- // if(abs(a-b)<eps) --> if(a==b)
- // fixed << setprecision(n) -->printing decimal till n
- // hypot(a ,b) --> sqrt(a^2 + b^2)
- void solve(){
- ll n ,r ,l;
- cin>>n>>r>>l;
- //its kind of 2 sat
- // like each (x,y) has two value (true or false)
- // assume true: horizontol and flase for vertical
- // for same row, if two of them overlap means they should not be true at same time
- // similar for row
- // (1...l) for true
- // i+l for flase
- // Then corresponding we make the graph and check strong connectivity
- vector<pair<ll,ll>>temp;
- vector<ll>adj[2*l] , rev_adj[2*l];
- for(int i=0;i<l;i++){
- ll x , y;
- cin>>x>>y;
- x--;
- y--;
- for(int j =0 ; j< temp.size();j++){
- if(temp[j].first == x){
- ll d = abs(temp[j].second - y);
- if(d >= 2*r+1) continue;
- // it means (i , j) can not be true at same time
- // or for 2sat (i+l , j+l) can not be false at same time
- adj[i].push_back(j+l);
- adj[j].push_back(i+l);
- rev_adj[j+l].push_back(i);
- rev_adj[i+l].push_back(j);
- }
- if(temp[j].second == y){
- ll d = abs(temp[j].first - x);
- if(d >= 2*r+1) continue;
- // it means (i , j) can not be false at same time (same for 2-sat)
- adj[i+l].push_back(j);
- adj[j+l].push_back(i);
- rev_adj[j].push_back(i+l);
- rev_adj[i].push_back(j+l);
- }
- }
- temp.push_back({x ,y});
- }
- //Now check strong connectivity
- vector<ll>order;
- vector<ll>vis(2*l);
- function<void(ll)> dfs=[&](ll node){
- vis[node] = 1;
- for(auto it : adj[node]){
- if(!vis[it]) dfs(it);
- }
- order.push_back(node);
- };
- for (int i = 0; i < 2*l; i++){
- if (!vis[i]){
- dfs(i);
- }
- }
- reverse(all(order));
- vis.assign(2*l, 0);
- vector<ll>component;
- function<void(ll)> dfs2=[&](ll node){
- vis[node] = 1;
- component.push_back(node);
- for(auto it : rev_adj[node]){
- if(!vis[it]) dfs2(it);
- }
- };
- for(auto it : order){
- if(!vis[it]){
- dfs2(it);
- //process the component
- unordered_map<ll,ll>mp;
- for(auto it : component){
- mp[it] = 1;
- }
- for(auto it : component){
- if(it < l && mp.count(it + l)){
- cout << "NO" <<endl;
- return;
- }
- }
- component.clear();
- }
- }
- cout << "YES" << endl;
- }
- int main(){
- JAI_SHREE_RAAM
- ll t =1;
- // cin>>t;
- for(int i=1;i<=t;i++){
- // cout<<"Case #"<<i<<": ";
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment