問題一覧 > 通常問題

No.3029 オイラー標数

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 61
作問者 : ジュ・ビオレ・グレイス / テスター : 👑 p-adic
0 ProblemId : 11907 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-02-21 21:56:49

問題文

三つの正整数からなるクエリ Aq Bq CqA_q \ B_q \ C_q が与えられます(q=1,,Qq = 1, \dots, Q)。ただし Aq<Bq<CqA_q < B_q < C_q です。
集合 V,E,FV, E, F を全てはじめ空集合にしておき、クエリ Aq Bq CqA_q \ B_q \ C_q に対して、次の操作を行います。

  • 3つの整数 Aq,Bq,CqA_q, B_q, C_qVV に追加する。
  • 3つの2元集合 {Aq,Bq},{Bq,Cq},{Cq,Aq}\{A_q, B_q\}, \{B_q, C_q\}, \{C_q, A_q\}EE に追加する。
  • 3元集合 {Aq,Bq,Cq}\{ A_q, B_q, C_q \}FF に追加する。

有限集合 XX の要素数を X|X| と表すことにして、QQ 個のクエリを処理したあとの V,E,FV, E, F について VE+F|V| - |E| + |F| を出力してください。

背景

幾何学では三次元の多面体について、点の数、辺の数、面の数をそれぞれ v,e,fv, e, f としたとき ve+fv - e + f をオイラー標数と言います。
これは多面体の「穴の個数」と関わりがあり、現代の位相幾何学の入口にある不変量です。
入力から作られる V,E,FV, E, F はそれぞれ多面体の点、辺、面(三角形)を集めたものと解釈できます。
このように、図形の点や辺、面の繋がり方だけを抽出したデータを「抽象単体複体」と言います。

入力

QQ
A1 B1 C1A_1 \ B_1 \ C_1
\vdots
AQ BQ CQA_Q \ B_Q \ C_Q

1Q105,1 \leq Q \leq 10^5,
1Aq<Bq<Cq108.1 \leq A_q < B_q < C_q \leq 10^8.

出力

最後に改行してください。

サンプル

サンプル1
入力
4
1 2 3
1 2 4
1 3 4
2 3 4
出力
2

V={1,2,3,4},V = \{ 1, 2, 3, 4 \},
E={{1,2},{1,3},{1,4},{2,3},{2,4},{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}}.F = \{ \{1,2,3\}, \{ 1,2,4 \}, \{1,3,4 \}, \{2,3,4 \} \}.
したがって、46+4=24 - 6 + 4 = 2 が出力されます。
この入力は四面体の各面を構成する頂点たちからなるクエリです。

サンプル2
入力
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
出力
0

これはトーラスという曲面の三角形分割を意図したクエリになっています。

この図では 11 という頂点や 1212 という辺などが複数個存在しますが、本来は一つしかなく(貼り合わせる)、二次元平面内で図示するためにあえて別々に描画しています。
V={1,2,3,4,5,6,7},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}},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={},F=14.F = \{ \dots \}, |F| = 14.
721+14=0.7 - 21 + 14 = 0.

サンプル3
入力
7
1 2 3
1 2 3
2 3 5
3 4 5
4 5 6
2 4 6
1 2 6
出力
0

V={1,2,3,4,5,6},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}}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={},F=6.F = \{ \dots \}, |F| = 6.
612+6=0.6 - 12 + 6 = 0.

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