BZOJ 4537: [Hnoi2016]最小公倍数

Description

给定一张N个顶点M条边的无向图(顶点编号为1,2,…,n),每条边上带有权值。所有权值都可以分解成2^a*3^b的形式。

现在有q个询问,每次询问给定四个参数u、v、a和b,请你求出是否存在一条顶点u到v之间的路径,使得路径依次经过的边上的权值的最小公倍数为2^a*3^b。

注意:路径可以不是简单路径。下面是一些可能有用的定义:最小公倍数:K个数a1,a2,…,ak的最小公倍数是能被每个ai整除的最小正整数。

路径:路径P:P1,P2,…,Pk是顶点序列,满足对于任意1<=i<k,节点Pi和Pi+1之间都有边相连。简单路径:如果路径P:P1,P2,…,Pk中,对于任意1<=s≠t<=k都有Ps≠Pt,那么称路径为简单路径。

Input

输入文件的第一行包含两个整数N和M,分别代表图的顶点数和边数。接下来M行,每行包含四个整数u、v、a、b代表一条顶点u和v之间、权值为2^a*3^b的边。接下来一行包含一个整数q,代表询问数。接下来q行,每行包含四个整数u、v、a和b,代表一次询问。询问内容请参见问题描述。

Output

对于每次询问,如果存在满足条件的路径,则输出一行Yes,否则输出一行 No(注意:第一个字母大写,其余字母小写) 。

Sample Input

4 5
1 2 1 3
1 3 1 2
1 4 2 1
2 4 3 2
3 4 2 2
5
1 4 3 3
4 2 2 3
1 3 2 2
2 3 2 2
1 3 4 4

Sample Output

Yes
Yes
Yes
No
No

HINT

1<=n,q<=50000、1<=m<=100000、0<=a,b<=10^9

Solution

分块+并查集。

首先想暴力怎么做?
对于每个询问我们把所有a<=query_a, b<=query_b的边都扔到并查集里维护一下就可以回答了。

标算采用了分块加速这个过程:

我们按照a的大小对边排序,分为若干块,同样按a的大小对询问排序。

然后从小到大找第一个没有回答的询问,定位到他所在的块,把这块之前的边都取出来按照b排个序,然后找到此次询问可以回答的其他询问,把这些询问拿出来也按照b排个序,然后对于这些询问:

  • Two-Pointer扫描该块之前的所有边
  • 暴力处理该块内的边

然后判断这个询问所在的联通快最大的a,b就可以了。

Source

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100005;
const int block_siz = 316;
const int block_cnt = maxn / block_siz + 10;
inline int getint() {
    register int r = 0; register bool b = true; register char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') b = false; c = getchar(); }
    while (c >= '0' && c <= '9') { r = (r<<1)+(r<<3) + c - '0'; c = getchar(); }
    return b ? r : -r;
}
struct edge_t { int u, v, a, b; } e[maxn], ee[maxn];
struct query_t { int u, v, a, b, id; } q[maxn];
struct modify_t { int id, fa, siz, mxa, mxb; } sta[maxn];
int n, m, Q, mxa[maxn], mxb[maxn], siz[maxn], fa[maxn], tail, mx[block_cnt + 9], L[block_cnt + 9], R[block_cnt + 9], ptr, ppp;
bool ans[maxn];
inline bool cmpea(const edge_t &x, const edge_t &y) { return x.a < y.a; }
inline bool cmpeb(const edge_t &x, const edge_t &y) { return x.b < y.b; }
inline bool cmpqa(const query_t &x, const query_t &y) { return x.a < y.a; }
inline bool cmpqb(const query_t &x, const query_t &y) { return x.b < y.b; }
inline int Find(int x) { while (fa[x] != x) x = fa[x]; return x; }
inline void Mer(int u, int v, int a, int b, bool o) {
    int x = Find(u), y = Find(v);
    if (x == y) {
        if (a > mxa[x] || b > mxb[x]) {
            if (o) sta[++tail] = modify_t{x, fa[x], siz[x], mxa[x], mxb[x]};
            mxa[x] = max(mxa[x], a);
            mxb[x] = max(mxb[x], b);
        }
    }
    else {
        if (siz[x] < siz[y]) swap(x, y);
        if (o) {
            sta[++tail] = modify_t{x, fa[x], siz[x], mxa[x], mxb[x]};
            sta[++tail] = modify_t{y, fa[y], siz[y], mxa[y], mxb[y]};
        }
        fa[y] = x;
        siz[x] += siz[y];
        mxa[x] = max(mxa[x], max(a, mxa[y]));
        mxb[x] = max(mxb[x], max(b, mxb[y]));
    }
}
inline void Undo(int i) {
    int x = sta[i].id;
    fa[x] = sta[i].fa;
    siz[x] = sta[i].siz;
    mxa[x] = sta[i].mxa;
    mxb[x] = sta[i].mxb;
}
inline bool Check(int u, int v, int a, int b) {
    int x = Find(u), y = Find(v);
    if (x != y) return false;
    if (mxa[x] < a || mxb[x] < b) return false;
    return true;
}
inline void Init() {
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
        siz[i] = 1;
        mxa[i] = -1;
        mxb[i] = -1;
    }
}
int main() {
    n = getint(); m = getint();
    for (int i = 1; i <= m; ++i) {
        e[i].u = getint();
        e[i].v = getint();
        e[i].a = getint();
        e[i].b = getint();
    }
    sort(e + 1, e + m + 1, cmpea);
    int cnt = (m + block_siz - 1) / block_siz;
    R[0] = 1;
    for (int i = 1; i <= cnt; ++i) {
        L[i] = R[i-1];
        R[i] = L[i] + block_siz;
        if (R[i] > m + 1) R[i] = m + 1;
        mx[i] = e[R[i] - 1].a;
    }
    Q = getint();
    for (int i = 1; i <= Q; ++i) {
        q[i].u = getint();
        q[i].v = getint();
        q[i].a = getint();
        q[i].b = getint();
        q[i].id = i;
    }
    sort(q + 1, q + Q + 1, cmpqa);
    ppp = 1;
    ptr = 1;
    Init();
    int i = 1;
    L[cnt + 1] = R[cnt + 1] = m + 1;
    mx[cnt + 1] = q[Q + 1].a = 2147483647;
    while (i <= Q) {
        while (mx[ptr] <= q[i].a) {
            Init();
            ppp = 1;
            sort(e + L[ptr], e + R[ptr], cmpeb);
            merge(e + 1, e + L[ptr], e + L[ptr], e + R[ptr], ee + 1, cmpeb);
            copy(ee + 1, ee + R[ptr], e + 1);
            ++ptr;
        }
        int ii = i + 1;
        while (mx[ptr] > q[ii].a) ++ii;
        sort(q + i, q + ii, cmpqb);
        while (i < ii) {
            while (ppp < L[ptr] && e[ppp].b <= q[i].b) {
                Mer(e[ppp].u, e[ppp].v, e[ppp].a, e[ppp].b, false);
                ++ppp;
            }
            for (int j = L[ptr]; j < R[ptr]; ++j)
                if (e[j].a <= q[i].a && e[j].b <= q[i].b)
                    Mer(e[j].u, e[j].v, e[j].a, e[j].b, true);
            ans[q[i].id] = Check(q[i].u, q[i].v, q[i].a, q[i].b);
            while (tail) Undo(tail--);
            ++i;
        }
    }
    for (int i = 1; i <= Q; ++i) {
        if (ans[i]) puts("Yes");
        else puts("No");
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据