1 条题解
-
1
#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
- 上传者