시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 1024 MB | 5 | 1 | 1 | 100.000% |
$\color{blue}{\text{LaLa}}$'s younger sister $\color{purple}{\text{LiLi}}$ is helping $\color{blue}{\text{LaLa}}$ cast the spirit summoning $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$.
While $\color{blue}{\text{LaLa}}$ was asleep, $\color{purple}{\text{LiLi}}$ had already built a prototype of the spirit to summon. The spirit consists of $N$ $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ joints which allow any $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ bars attached to them to freely move around them, and $M$ $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ bars of various colors, each of which connects two $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ joints and whose length can be adjusted to any non-negative real number before the summoning (but not after).
When it comes to spirit summoning, $\color{blue}{\text{LaLa}}$ has a far higher standard than $\color{purple}{\text{LiLi}}$. Of course, $\color{blue}{\text{LaLa}}$ was not satisfied with $\color{purple}{\text{LiLi}}$'s work whatsoever. $\color{blue}{\text{LaLa}}$ would like to fabulize the prototype by getting rid of some $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ bars so that
Write a program that computes the degree of freedom of the spirit fabulized by $\color{blue}{\text{LaLa}}$.
The input describes the prototype spirit made by $\color{purple}{\text{LiLi}}$ and is given in the following format:
$N$ $M$
$u_0$ $v_0$ $c_0$
$u_1$ $v_1$ $c_1$
$\vdots$
$u_{M-1}$ $v_{M-1}$ $c_{M-1}$
where $N$ is the number of $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ joints, numbered from $0$ to $N-1$, $M$ is the number of $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ bars, and for each integer $0 \le i < M$, the $i$-th $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ bar has color $c_i$ and connects the $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ joint $u_i$ and $v_i$.
The input satisfies the following constraints:
Note that there can be multiple $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ bars connecting the same pair of $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ joints.
The output should be a single integer equal to the degree of freedom of the spirit fabulized by $\color{blue}{\text{LaLa}}$.
3 3 0 1 0 0 2 0 1 2 0
5
3 3 0 1 0 0 2 1 1 2 2
3
4 4 0 1 0 1 2 1 2 3 2 0 3 3
4
5 4 0 1 0 1 2 1 2 3 2 3 4 3
6
Intuitively, the degree of freedom is the number of axis of motions preserving edge lengths of the spirit embedded on a plane.
More formally, let $E$ be an assignment of planar coordinates (we'll call this an embedding) to all $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ joints of a spirit. Note that such an embedding can be identified with an element in $\mathbb{R}^{2N}$ by concatenating all coordinates, where $N$ is the number of $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ joints.
Let $C(E)$ be the set of embeddings continuously reachable from $E$ as an element of $\mathbb{R}^{2N}$ while preserving edge lengths. i.e. for each element $E'$ of $C(E)$ and each $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ bars of the spirit connecting magic joints $u$ and $v$, the euclidean distance between $u$ and $v$ must be the same in $E$ and $E'$.
The degree of freedom of $E$ is the minimum non-negative integer $k$ such that there exists a continuous bijective mapping $F:D \rightarrow C(E)$ where $D$ is a connected subset of $\mathbb{R}^k$.
The degree of freedom of a spirit is the maximum degree of freedom over all such embeddings $E$.
The following illustrate the spirit fabulized by $\color{blue}{\text{LaLa}}$ along with one of the optimal embedding and the mapping $F$ for each sample tests in order.
$k = 5$, $D = \mathbb{R}^2 \times [0, 2\pi) \times \mathbb{R}^2$
$F: (x_0, x_1, x_2, x_3, x_4) \mapsto \langle(x_0, x_1), (x_0, x_1) + (\cos{x_2}, \sin{x_2}), (x_3, x_4)\rangle$
The following illustrates the 5 degrees of freedom associated with each variables.
$k = 3$, $D = \mathbb{R}^2 \times [0, 2\pi)$
$F: (x_0, x_1, x_2) \mapsto \langle(x_0, x_1), (x_0, x_1) + (\cos{x_2}, \sin{x_2}), (x_0, x_1) + (\cos{(\frac{\pi}{3} + x_2)}, \sin{(\frac{\pi}{3} + x_2)})\rangle$
The following illustrates the 3 degrees of freedom associated with each variables.
$k = 4$, $D = \mathbb{R}^2 \times (((0, 2] \times [0, 2\pi)) \cup (\lbrace 0 \rbrace \times [0, \pi)))$
$F: (x_0, x_1, x_2, x_3) \mapsto \langle P_0, P_0 + \frac{x_2}{2} P_1 + \sqrt{1 - \frac{x_2^2}{4}} P_2, P_0 + x_2 P_1, P_0 + \frac{x_2}{2} P_1 - \sqrt{1 - \frac{x_2^2}{4}} P_2\rangle$
where $P_0 = (x_0, x_1), P_1 = (\cos{x_3}, \sin{x_3})$ and $P_2 = (\sin{x_3}, -\cos{x_3})$.
The following figure on the left illustrates the 4 degrees of freedom associated with each variables. Note that the motion associated with the variable $x_2$ is non-rigid. The one on the right illustrates the motion associated with $x_2$ in detail.
$k = 6$, $D = \mathbb{R}^2 \times [0, 2\pi)^4$
$F: (x_0, x_1, x_2, x_3, x_4, x_5) \mapsto \langle P_0, P_1, P_2, P_3, P_4 \rangle$
where $P_0 = (x_0, x_1)$ and $P_i = P_{i-1} + (\cos{x_{i + 1}}, \sin{x_{i + 1}})$ for all integers $1 \le i \le 4$.
The following illustrates the 6 degrees of freedom associated with each variables.
Camp > Osijek Competitive Programming Camp > Winter 2023 > Day 9: Magical Story of LaLa I번