No.3784 01 Walk
タグ : / 解いたユーザー数 6
作問者 :
Problem Statement
There is a directed graph with $N$ vertices and $M$ edges. The vertices are numbered with integers from $1$ to $N$, and the edges are numbered with integers from $1$ to $M$. For $1\le i\le M$, edge $i$ is directed from vertex $u_i$ to vertex $v_i$ and has an integer $c_i$ written on it. Here, $c_i \in \{0,1\}$. Initially, a piece is placed on vertex $1$.
There is a sequence $A$, and initially $A$ is empty. You may now perform the following operation any number of times, $0$ or more.
- Suppose the piece is currently on vertex $x$. Choose $1$ edge $e$ such that $u_e=x$, and move the piece to vertex $v_e$. Then, if $A$ is empty or the last element of $A$ differs from $c_e$, append the integer $c_e$ to the end of $A$. Otherwise, (without performing the operation of appending $c_e$) delete the current last element of $A$.
However, if the out-degree of vertex $x$ is $0$, the operation cannot be performed.
For each of $k=1,2,\cdots ,N$, find the maximum possible length of $A$ in a state where the piece is on vertex $k$.
If the maximum does not exist, output -1 instead.
Note that the constraints guarantee that, for every vertex $v$ with $1\le v\le N$, vertex $v$ is reachable from vertex $1$; that is, there exists a sequence of operations that places the piece on vertex $v$.
Constraints
- $1\le N\le 2\times 10^5$
- $0\le M\le 2\times 10^5$
- $1\le u_i,v_i\le N\ (1\le i\le M)$
- $c_i \in \{0,1\}\ (1\le i\le M)$
- $(u_i,v_i,c_i) \neq (u_j,v_j,c_j)\ (1\le i < j\le M)$
- For every vertex $v$ with $1\le v\le N$, vertex $v$ is reachable from vertex $1$
- All input values are integers
Input
The input is given in the following format.
$N\ M$ $u_1\ v_1\ c_1$ $u_2\ v_2\ c_2$ $\vdots$ $u_M\ v_M\ c_M$
Output
Output $N$ lines. On the $i$-th line $(1\le i\le N)$, output the maximum length of $A$ in a state where the piece is on vertex $i$ (or -1 if it does not exist).
Print a newline at the end.
Sample
Sample 1
Input
6 7 1 2 1 2 3 0 3 4 1 4 2 0 1 5 1 5 6 1 6 5 0
Output
0 4 3 3 -1 -1
For example, the following operations achieve a length of $3$ for $A$ with the piece on vertex $3$.
- Choose edge $1$ and move the piece from vertex $1$ to vertex $2$. Now $A=(1)$.
- Choose edge $2$ and move the piece from vertex $2$ to vertex $3$. Now $A=(1,0)$.
- Choose edge $3$ and move the piece from vertex $3$ to vertex $4$. Now $A=(1,0,1)$.
- Choose edge $4$ and move the piece from vertex $4$ to vertex $2$. Now $A=(1,0,1,0)$.
- Choose edge $2$ and move the piece from vertex $2$ to vertex $3$. Now $A=(1,0,1)$.
Also, by first choosing edge $5$ and then alternately choosing edge $6$ and edge $7$, the length of $A$ can be made arbitrarily large while moving the piece between vertex $5$ and vertex $6$.
Therefore, the answer for vertices $5,6$ is -1.
Sample 2
Input
10 13 1 2 1 2 3 1 3 4 0 4 1 0 2 7 0 3 6 1 4 10 0 10 5 1 5 6 1 6 7 0 7 8 1 8 9 1 9 5 0
Output
0 1 0 1 1 1 2 3 2 0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。