题解 CF1322C 【Instant Noodles】

xht · 2020-03-09 23:32:58 · 题解

对于右部点 i，设 S(i) 表示所有与其相连的左部点的集合。

对于 i，若 |S(i)| = 0，则可以直接扔掉。

对于 i,j，若 S(i) = S(j)，则这两个点可以合并为一个，合并后的点的权值为原先两点权值之和。

合并后，所有点的 S(i) 均不为空集且互不相同，此时对所有点的权值求 \gcd 即可。

判断 S(i) = S(j) 时需要 hash 一下。

const int N = 5e5 + 7;
int n, m, B, P;
ll a[N];
vi e[N];

inline int h(vi p) {
    sort(p.begin(), p.end());
    int ret = 0;
    for (int x : p) ret = (1ll * ret * B + x) % P;
    return ret;
}

inline void solve() {
    rd(n), rd(m), rda(a, n);
    for (int i = 1; i <= n; i++) e[i].clear();
    for (int i = 1, x, y; i <= m; i++) rd(x), rd(y), e[y].pb(x);
    map<int, ll> p;
    for (int i = 1; i <= n; i++)
        if (e[i].size()) p[h(e[i])] += a[i];
    ll d = 0;
    for (auto o : p) d = d ? __gcd(d, o.se) : o.se;
    print(d);
}

int main() {
    srand(time(0));
    P = rdm((int)1e8, (int)1e9);
    B = rdm((int)1e7, (int)1e8);
    int T;
    rd(T);
    while (T--) solve();
    return 0;
}