Type: Div1C https://codeforces.com/contest/1322/problem/C
Given a bipartite graph of n
vertices (labelled 1
to N
) and m
edges. Let L
and R
be the disjoint set of vertices. Formally, "disjoint" means that there exists no x
and y
such that x ∈ L
and y ∈ R
and edge (x, y)
exists. Each vertex i
has a value c[i]
.
For all S ∈ L
, N(S)
is the set of vertices in R
adjacent to any vertex in S
.
For all S ∈ L
, f(S)
is the sum of all c[i]
for all vertex in N(S)
.
The task is to compute the gcd of f(S)
over all S ∈ L
.
gcd is the greatest common divisor and the gcd of an empty set is 0.
-
We only need to consider unique sets of values of
f(S)
. Repeated values will not affect the gcd. -
We need to somehow enumerate the possible sums that can occur.
-
Some sums of vertices in
R
cannot occur. -
Enumeration of sums can be done in an incremental manner. That is, to add and not to add some vertex. But this could be subject to some constraints.
-
Some pair of vertices can be tied together. Meaning, that if vertex
x
is in someN(S)
, then vertexy
must be in it as well. The necessary condition for this to happen is that vertexx
and vertexy
must have the exactly same neighbouring set inL
. The neighboring set of some a vertex inR
is the set of all vertices inL
that it's adjacent to.If
x
andy
have different neighbouring sets, then you can choose to include only one of them in some partial set of vertices. -
If some vertices are tied together, then we can treat them as a single vertex. Hence, we group all vertices of the same neighboring set and turn them into a single vertex with its value being the sum of
c[i]
's.
- Now that we have built a reduced set of vertices in
R
, we can incrementally build sums without constraints. That is, all possible combinations ofadd
andnot add
can happen. This is just the subset sum of the values.
- What is the gcd of all subset sums of a given set of values? Well, it has to be at least the gcd of single-element subsets - let this value of be G. We know that when we start to enumerate subsets of size 2, 3, 4, these sums are divisible by
G
. Why? Because they are sums of numbers that are divisible byG
. Now, can it be higher thanG
? No, because gcd cannot increase when you consider more numbers.
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
vector< vector<int> > adj(n);
vector<long long> c(n);
for (int i = 0; i < n; i++) cin >> c[i];
for (int i = 0, x, y; i < m; i++) {
cin >> x >> y;
adj[--y].push_back(--x);
}
map<vector<int>, long long> group;
for (int i = 0; i < n; i++) {
if (adj[i].empty()) continue;
sort(adj[i].begin(), adj[i].end());
group[adj[i]] += c[i];
}
long long g = 0;
for (auto e : group) g = gcd(g, e.second);
cout << g << '\n';
}