1 条题解

  • 1
    @ 2022-8-21 21:53:24
    #include <bits/stdc++.h>
    using namespace std;
    constexpr int N = 50'000, M = 100'000, Q = 50'000;
    struct Edge {
        int u, v, a, b;
    };
    struct Query {
        int u, v, a, b, id;
    };
    int fa[N], mxa[N], mxb[N];
    Edge edge[M];
    vector<Query> query[M];
    vector<tuple<int, int, int>> e[N];
    int id[N], stk[N], que[N];
    bool ans[Q], vis[N], used[N];
    int find(int x) {
        while (fa[x] >= 0 && fa[fa[x]] >= 0)
            x = fa[x] = fa[fa[x]];
        return fa[x] >= 0 ? fa[x] : x;
    }
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        int n, m, q;
        cin >> n >> m;
        memset(id, -1, n * sizeof(int));
        for (int i = 0; i < m; ++i) {
            cin >> edge[i].u >> edge[i].v >> edge[i].a >> edge[i].b;
            --edge[i].u;
            --edge[i].v;
        }
        sort(edge, edge + m, [&](const Edge &lhs, const Edge &rhs) {
            return lhs.a < rhs.a;
        });
        cin >> q;
        int sz = 1.5 * m / sqrt(q);
        int blocks = (m + sz - 1) / sz;
        for (int i = 0; i < q; ++i) {
            int u, v, a, b;
            cin >> u >> v >> a >> b;
            --u;
            --v;
            int j = 0;
            while (j + 1 < blocks && edge[sz * j + sz - 1].a <= a)
                ++j;
            query[j].push_back(Query{u, v, a, b, i});
        }
        for (int bl = 0; bl < blocks; ++bl) {
            memset(fa, -1, n * sizeof(int));
            memset(mxa, -1, n * sizeof(int));
            memset(mxb, -1, n * sizeof(int));
            int i = 0;
            sort(edge, edge + sz * bl, [&](const auto &lhs, const auto &rhs) {
                return lhs.b < rhs.b;
            });
            sort(query[bl].begin(), query[bl].end(), [&](const auto &lhs, const auto &rhs) {
                return lhs.b < rhs.b;
            });
            for (auto &&q : query[bl]) {
                while (i < sz * bl && edge[i].b <= q.b) {
                    int u = find(edge[i].u);
                    int v = find(edge[i].v);
                    if (u != v) {
                        if (fa[u] > fa[v])
                            swap(u, v);
                        fa[u] += fa[v];
                        mxa[u] = max(mxa[u], mxa[v]);
                        mxb[u] = max(mxb[u], mxb[v]);
                        fa[v] = u;
                    }
                    mxa[u] = max(mxa[u], edge[i].a);
                    mxb[u] = max(mxb[u], edge[i].b);
                    ++i;
                }
                int stkTop = 0;
                int u = find(q.u);
                used[u] = true;
                stk[stkTop++] = u;
                int v = find(q.v);
                if (u != v) {
                    used[v] = true;
                    stk[stkTop++] = v;
                }
                for (int j = sz * bl; j < m && j < sz * (bl + 1); ++j) {
                    if (edge[j].a <= q.a && edge[j].b <= q.b) {
                        int u = find(edge[j].u);
                        int v = find(edge[j].v);
                        if (!used[u]) {
                            used[u] = true;
                            stk[stkTop++] = u;
                        }
                        if (!used[v]) {
                            used[v] = true;
                            stk[stkTop++] = v;
                        }
                        e[u].emplace_back(v, edge[j].a, edge[j].b);
                        e[v].emplace_back(u, edge[j].a, edge[j].b);
                    }
                }
                int queL = 0, queR = 0;
                que[queR++] = u;
                vis[u] = true;
                int ma = -1, mb = -1;
                while (queL < queR) {
                    int u = que[queL++];
                    ma = max(ma, mxa[u]);
                    mb = max(mb, mxb[u]);
                    for (auto &&ed : e[u]) {
                        int v, a, b;
                        tie(v, a, b) = ed;
                        ma = max(ma, a);
                        mb = max(mb, b);
                        if (!vis[v]) {
                            vis[v] = true;
                            que[queR++] = v;
                        }
                    }
                }
                ans[q.id] = vis[v] && ma == q.a && mb == q.b;
                for (int j = 0; j < stkTop; ++j) {
                    int u = stk[j];
                    used[u] = vis[u] = false;
                    e[u].clear();
                }
            }
        }
        for (int i = 0; i < q; ++i)
            cout << (ans[i] ? "Yes" : "No") << "\n";
        return 0;
    }
    
    • 1

    信息

    ID
    2183
    时间
    3000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    17
    已通过
    3
    上传者