A Graph Problem
다이아몬드 V의견: 0
To improve her mathematical knowledge, Bessie has been taking a graph theory
course and finds herself stumped by the following problem. Please help her!
You are given a connected, undirected graph with vertices labeled \(1\dots N\) and
edges labeled \(1\dots M\) (\(2\le N\le 2\cdot 10^5\), \(N-1\le M\le 4\cdot 10^5\)).
For each vertex \(v\) in the graph, the following process is conducted:
- Let \(S=\{v\}\) and \(h=0\).
- While \(|S|
- Add the endpoint of \(e\) not in \(S\) to \(S\).
- Set \(h=10h+e\).
Return \(h\pmod{10^9+7}\).
Determine all the return values of this process.
Problem credits: Benjamin Qi
SCORING
- Input 4: \(N,M\le 2000\)
- Inputs 5-6: \(N\le 2000\)
- Inputs 7-10: \(N\le 10000\)
- Inputs 11-14: \(a_e+1=b_e\) for all \(e\)
- Inputs 15-23: No additional constraints.
Problem credits: Benjamin Qi
The first line contains \(N\) and \(M\).
Then follow \(M\) lines, the \(e\)th containing the endpoints \((a_e,b_e)\) of the
\(e\)th edge (\(1\le a_e
connected graph, and at most one edge connects each pair of vertices.
Output \(N\) lines, where the \(i\)th line should contain the return value of the
process starting at vertex \(i\).
3 2
1 2
2 312
12
215 6
1 2
3 4
2 4
2 3
2 5
1 51325
1325
2315
2315
5132Consider starting at \(i=3\). First, we choose edge \(2\), after which
\(S = \{3, 4\}\) and \(h = 2\). Second, we choose edge \(3\), after which
\(S = \{2, 3, 4\}\) and \(h = 23\). Third, we choose edge \(1\), after which
\(S = \{1, 2, 3, 4\}\) and \(h = 231\). Finally, we choose edge \(5\), after which
\(S = \{1, 2, 3, 4, 5\}\) and \(h = 2315\). The answer for \(i=3\) is therefore
\(2315\).
15 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15678925929
678925929
678862929
678787329
678709839
678632097
178554320
218476543
321398766
431520989
542453212
653475435
764507558
875540761
986574081Make sure to output the answers modulo \(10^9+7\).
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > December > Platinum
평가 및 의견
A Graph Problem
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
A Graph Problem