SS6 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Sandeep Singh
Tester: Sunita Sen

DIFFICULTY:

Medium

PREREQUISITES:

Disjoint set union, sorting

EXPLANATION:

We will solve the queries offline. Store all the queries in increasing order of S in an array and all nodes weight along with node number sorted in increasing order of weight in another array. For each query, we will check all nodes where W <= S of that query. While checking we will use DSU to join nodes.

Checking here means visiting all the neighboring nodes of the current node and join the current node with the neighbors whose weight is less than equal to the weight of the current node. Once we have checked all nodes with weight less than equal to the S of the current query, we are ready to answer this query. If the X and Y of the current query are in the same group in DSU structure, then the answer is “YES”, else “NO”. This is so because they will be in the same group only if there is at least 1 path where all nodes have a value less than equal to the S of the current node.

Time Complexity: O(NlogN)

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
#define ll long long 
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ln cout << '\n'
#define mod 1000000007
#define MxN 100005
#define all(x) x.begin(), x.end()
using namespace std;
class dsu {
 public:
  vector <int> p;
  int n;
 
  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }
 
  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }
 
  inline void unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) 
      p[x] = y;
    
  }
};
vector <int> g[MxN];
vector <int> arr(MxN);
struct qry{
    int x, y, s, idx;
};
 
bool cmp(qry& A, qry& B){
    return A.s < B.s;
}
void solve(){
 
    int i, j, n, m, q;
    cin >> n >> m >> q;
    vector <string> ans(q);
    vector <bool> active(MxN, 0);
    vector<pair<int, int>> nodes;
    dsu d = dsu(MxN);
 
    for(i = 1; i <= n; ++i){ 
        cin >> arr[i];
        nodes.push_back({arr[i], i});
    };
 
    for(i = 0; i < m; ++i){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<qry> queries;
 
    for(i = 0; i < q; ++i){
        int x, y, s;
        cin >> x >> y >> s;
        queries.push_back({x, y, s, i});
    }
    sort(queries.begin(), queries.end(), cmp);
    sort(all(nodes));
    int nodectr = 0;
 
    for(i = 0; i < q; ++i){
        int power = queries[i].s; 
 
        while(nodectr < n && nodes[nodectr].first <= power){
 
            int u = nodes[nodectr].second;
            active[u] = 1;
 
            for(int child: g[u]){
 
                if(active[child])
                    d.unite(child, u);
            }
            ++nodectr;
        }
        ans[queries[i].idx] = (d.get(queries[i].x) == d.get(queries[i].y))?"YES": "NO";
    }
 
    for(i = 0; i < q; ++i)
        cout << ans[i] << '\n';
    
}
int main(){
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
 
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
    #endif
 
    int t = 1;
    //cin >> t;
    while(t--)
        solve();
}
1 Like