【MST+离线】CF1851 G

刺骨的言语ヽ痛彻心扉 2024-03-22 21:20 44阅读 0赞

[Problem - G - Codeforces][]

题意：

![721e7beffa0846be9ac132457e59015c.png][]

![92bc92a79fcf4a92ac15b10a098b43fd.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int N=2e5+10;
    const int mod=1e9+7;
    
    int a[N];
    struct node {
        int x, y, val;
        bool operator < (const node &k) const {
            return val < k.val;
        }
    }b[N];
    struct Que {
        int x, y, val;
        int pos;
        bool operator < (const Que &k) const {
            return val < k.val;
        }
    }que[N];
    bool ok[N];
    int fa[N];
    int getf(int x) {
        if (x == fa[x]) return x;
        return fa[x] = getf(fa[x]);
    }
    void solve(){
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for (int i = 1; i <= m; i++) {
            int x, y, val;
            cin >> x >> y;
            val = max(a[x], a[y]);
            b[i] = {x, y, val};
        }
        sort(b + 1, b + 1 + m);
        for (int i = 1; i <= n; i++) {
            fa[i] = i;
        }
        int q;
        cin >> q;
        for (int i = 1; i <= q; i++) {
            int x, y, val;
            cin >> x >> y >> val;
            que[i] = {x, y, val + a[x], i};
        }
        sort(que + 1, que + 1 + q);
        int r = 1;
        for (int i = 1; i <= q; i++) {
            while(r <= m && b[r].val <= que[i].val) {
                int fx = getf(b[r].x), fy = getf(b[r].y);
                r++;
                if (fx == fy) continue;
                fa[fx] = fy;
            }
            ok[que[i].pos] = (getf(que[i].x) == getf(que[i].y));
        }
        for (int i = 1; i <= q; i++) {
            if (ok[i]) cout << "YES\n";
            else cout << "NO\n";
        }
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - G - Codeforces]: https://codeforces.com/contest/1851/problem/G
[721e7beffa0846be9ac132457e59015c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/891091a6e0de42f4befd6a36df79a4d4.png
[92bc92a79fcf4a92ac15b10a098b43fd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/7baf638102f04097bf551425049bbaa6.png