問題一覧 > 通常問題

No.3029 Euler Characteristic

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 70
作問者 : ジュ・ビオレ・グレイス / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 11907 / 自分の提出
問題文最終更新日: 2025-02-21 21:56:49
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 457 (順位表) の他の問題:

Problem Statement

You are given queries $A_q \ B_q \ C_q$, each consisting of three positive integers ($q = 1, \dots, Q$), where $A_q < B_q < C_q$.
Initially, the sets $V, E, F$ are all empty. For each query $A_q \ B_q \ C_q$, perform the following operations.

  • Add the three integers $A_q, B_q, C_q$ to $V$.
  • Add the three 2-element sets $\{A_q, B_q\}, \{B_q, C_q\}, \{C_q, A_q\}$ to $E$.
  • Add the 3-element set $\{ A_q, B_q, C_q \}$ to $F$.

Let $|X|$ denote the number of elements of a finite set $X$. Output $|V| - |E| + |F|$ for $V, E, F$ after processing all $Q$ queries.

Background

In geometry, for a three-dimensional polyhedron with $v, e, f$ vertices, edges, and faces respectively, the value $v - e + f$ is called the Euler characteristic.
It is related to the "number of holes" of the polyhedron, and is an invariant found at the entrance to modern topology.
The sets $V, E, F$ constructed from the input can be interpreted as collections of the vertices, edges, and faces (triangles) of a polyhedron, respectively.
Data like this, which extracts only how the vertices, edges, and faces of a figure are connected, is called an "abstract simplicial complex".

Input

$Q$
$A_1 \ B_1 \ C_1$
$\vdots$
$A_Q \ B_Q \ C_Q$

$1 \leq Q \leq 10^5,$
$1 \leq A_q < B_q < C_q \leq 10^8.$

Output

Print a newline at the end.

Sample

Sample 1
Input
4
1 2 3
1 2 4
1 3 4
2 3 4
Output
2

$V = \{ 1, 2, 3, 4 \},$
$E = \{ \{1, 2 \}, \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{3, 4\} \},$
$F = \{ \{1,2,3\}, \{ 1,2,4 \}, \{1,3,4 \}, \{2,3,4 \} \}.$
Therefore, $4 - 6 + 4 = 2$ is output.
The queries in this input consist of the vertices forming each face of a tetrahedron.

Sample 2
Input
14
1 2 4
5 6 7
4 6 7
1 5 6
2 3 7
1 3 7
2 4 5
2 5 7
1 4 7
1 2 6
2 3 6
3 4 6
3 4 5
1 3 5
Output
0

These queries are intended as a triangulation of a surface called the torus.

In this figure, items such as the vertex $1$ and the edge $12$ appear multiple times, but there is actually only one of each (they are glued together); they are deliberately drawn separately in order to depict the surface in a two-dimensional plane.
$V = \{ 1, 2, 3, 4, 5, 6, 7 \},$
$E = \{ \{4, 6\}, \{3, 7\}, \{1, 5\}, \{4, 5\}, \{5, 7\}, \{1, 3\}, \{1, 4\}, \{2, 4\}, \{2, 3\}, \{3, 6\}, \{1, 7\}, \{1, 2\}, \{4, 7\}, \{2, 7\}, \{3, 5\}, \{2, 6\}, \{2, 5\}, \{6, 7\}, \{1, 6\}, \{3, 4\}, \{5, 6\} \},$
$F = \{ \dots \}, |F| = 14.$
$7 - 21 + 14 = 0.$

Sample 3
Input
7
1 2 3
1 2 3
2 3 5
3 4 5
4 5 6
2 4 6
1 2 6
Output
0

$V = \{ 1, 2, 3, 4, 5, 6 \},$
$E = \{ \{4, 6\}, \{4, 5\}, \{3, 5\}, \{1, 3\}, \{2, 4\}, \{2, 3\}, \{1, 2\}, \{2, 6\}, \{2, 5\}, \{1, 6\}, \{3, 4\}, \{5, 6\} \}$
$F = \{ \dots \}, |F| = 6.$
$6 - 12 + 6 = 0.$

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。