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

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

問題へのリンク

問題概要

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

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

• と隣接している右頂点の値の総和

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

制約

• 
• 
• クエリごとの の総和が 以下

考えたこと

結局、

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

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

#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());
    }
}