けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces Round #626 (Div. 1) C. Instant Noodles

割と TLE に関して危険な橋をわたっていたのかもしれない。でも、ロリハとかしなくても大丈夫だった。

問題へのリンク

問題概要

左頂点数と右頂点数がともに  N であるような二部グラフが与えられる。二部グラフの辺数は  M である。

右頂点  v には値  c_{v} がある。今、左頂点集合の空でない部分集合  S に対して

  •  f(S) := S と隣接している右頂点の値の総和

とする。空でないあらゆる  S に対する  f(S) の値の最大公約数を求めよ (というクエリが  T 回)

制約

  •  1 \le T \le 5 \times 10^{5}
  •  1 \le N, M \le 5 \times 10^{5}
  • クエリごとの  M の総和が  5 \times 10^{5} 以下

考えたこと

結局、

  • 各右頂点について、「それと隣接している左頂点の集合」がまったく等しい部分はマージ (値も合算) してしまってよい
  • そして、マージ後の各値の最大公約数を求める

とすれば OK。マージ処理は map<set, long long> 型でやった。キーの set 部分に登場する要素数の総和が  M 以下なので、十分間に合うと踏んだ。不安ならローリングハッシュを用いてハッシュ化するのがよさそう。こういうの悩む。

#include <bits/stdc++.h>
using namespace std;

long long GCD(long long a, long long b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}

using pint = pair<int,int>;
int N, M;
vector<long long> C;
vector<set<int>> G;

long long solve() {
    map<set<int>, long long> ma;
    for (int i = 0; i < N; ++i) ma[G[i]] += C[i];
    long long res = 0;
    for (auto it : ma) {
        if (it.first.empty()) continue;
        res = GCD(res, it.second);
    }
    return res;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &N, &M);
        C.resize(N);
        G.assign(N, set<int>());
        for (int i = 0; i < N; ++i) scanf("%lld", &C[i]);
        for (int i = 0; i < M; ++i) {
            int u, v;
            scanf("%d %d", &u, &v);
            --u, --v;
            G[v].insert(u);
        }
        printf("%lld\n", solve());
    }
}