Sum of Distances
다이아몬드 V의견: 0
Bessie has a collection of connected, undirected graphs \(G_1,G_2,\ldots,G_K\)
(\(2\le K\le 5\cdot 10^4\)). For each \(1\le i\le K\), \(G_i\) has exactly \(N_i\)
(\(N_i\ge 2\)) vertices labeled \(1\ldots N_i\) and \(M_i\) (\(M_i\ge N_i-1\)) edges.
Each \(G_i\) may contain self-loops, but not multiple edges between the same pair
of vertices.
Now Elsie creates a new undirected graph \(G\) with \(N_1\cdot N_2\cdots N_K\)
vertices, each labeled by a \(K\)-tuple \((j_1,j_2,\ldots,j_K)\) where
\(1\le j_i\le N_i\). In \(G\), two vertices \((j_1,j_2,\ldots,j_K)\) and
\((k_1,k_2,\ldots,k_K)\) are connected by an edge if for all \(1\le i\le K\), \(j_i\)
and \(k_i\) are connected by an edge in
\(G_i\).
Define the distance between two vertices in \(G\) that lie in the same
connected component to be the minimum number of edges along a path from one
vertex to the other. Compute the sum of the distances between vertex
\((1,1,\ldots,1)\) and every vertex in the same component as it in \(G\), modulo
\(10^9+7\).
Problem credits: Benjamin Qi
SCORING
- Test cases 3-4 satisfy \(\prod N_i\le 300\).
- Test cases 5-10 satisfy \(\sum N_i\le 300\).
- Test cases 11-20 satisfy no additional constraints.
Problem credits: Benjamin Qi
The first line contains \(K\), the number of graphs.
Each graph description starts with \(N_i\) and \(M_i\) on a single line, followed by
\(M_i\) edges.
Consecutive graphs are separated by newlines for readability. It is guaranteed
that \(\sum N_i\le 10^5\) and \(\sum M_i\le 2\cdot 10^5\).
The sum of the distances between vertex \((1,1,\ldots,1)\) and every vertex that
is reachable from it, modulo \(10^9+7\).
2
2 1
1 2
4 4
1 2
2 3
3 4
4 14\(G\) contains \(2\cdot 4=8\) vertices, \(4\) of which are not connected to vertex
\((1,1)\). There are \(2\) vertices that are distance \(1\) away from \((1,1)\) and \(1\)
that is distance \(2\) away. So the answer is \(2\cdot 1+1\cdot 2=4\).
3
4 4
1 2
2 3
3 1
3 4
6 5
1 2
2 3
3 4
4 5
5 6
7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1706\(G\) contains \(4\cdot 6\cdot 7=168\) vertices, all of which are connected to
vertex \((1,1,1)\). The number of vertices that are distance \(i\) away from
\((1,1,1)\) for each \(i\in [1,7]\) is given by the \(i\)-th element of the following
array:
\([4,23,28,36,40,24,12]\).
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > January > Platinum
평가 및 의견
Sum of Distances
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Sum of Distances