1 - 建設事業 (Construction Project)

Time Limit: 5 sec / Memory Limit: 256 MiB

配点 : 100 点

問題文

IOI 国では交通網の一斉整備を行うことになった.IOI 国は xy 座標平面として表され,その上に N 個の町がある.i 番目 (1 \leqq i \leqq N) の町は点 (X_{i}, Y_{i}) として表される.交通網の整備は次の手順で行われる.

  • N 個の町のうちいくつかの町に国際空港を建設する.少なくとも 1 つは国際空港を建設する必要がある.国際空港は 1 つ建設するごとに決まったコストがかかる.
  • 町どうしを結ぶ道路をいくつか敷設する.道路は町を表す点どうしを直接結ぶ x 軸か y 軸に平行な線分であり,道路は 1 本敷設するごとにその長さと同じぶんのコストがかかる.

このとき,次の条件が満たされていなければならない.

  • IOI 国には地盤の状態が悪いなどの理由で道路を敷設できない領域が M 個ある.各領域は長方形で表され,j 番目 (1 \leqq j \leqq M) の長方形の左下の点は (P_{j}, Q_{j}) であり右上の点は (R_{j}, S_{j}) である (すなわち P_{j} < R_{j} かつ Q_{j} < S_{j} である).どの道路も,M 個の領域のうちいずれのものとも共通部分をもってはいけない.領域は周上も含むものとし,領域を表す長方形の周と共通部分を持つような道路も存在してはいけない.
  • N 個のどの町からも,道路を辿って別の町へ行くことを繰り返して国際空港のある町へ辿りつける必要がある.

この事業の発注先として建設会社 C 社が候補に挙がっている.k 番目 (1 \leqq k \leqq C) の建設会社は国際空港を 1 つ建設するのにコスト B_{k} がかかり,最大で H_{k} 個までの国際空港を建設できる (道路の建設にかかるコストは建設会社によらず,また道路の本数や長さに制限はない).それぞれの建設会社に対して,その建設会社が上の条件を満たすように交通網の整備を行うときにかかるコストの合計値の最小値を求めたい.

建設できる国際空港の個数が小さいために,条件を満たすような交通網の整備を行えない建設会社があるかもしれない.その場合はコストの合計値ではなく,条件を満たせないということを報告してほしい.

課題

IOI 国の町の数を表す整数 N と町の座標,道路を敷設できない領域の数を表す整数 M とそれぞれの領域を表す座標,発注先候補の建設会社の数を表す整数 C とそれぞれの建設会社の情報が与えられたとき,それぞれの建設会社に対して問題文中で述べられた条件を満たすように交通網の整備を行うときにかかるコストの合計値の最小値を求めるプログラムを作成せよ.

入力

標準入力から以下の入力を読み込め.

  • 1 行目には 3 つの整数 N, M, C が空白を区切りとして書かれており,それぞれ IOI 国にある町の個数,道路を敷設できない領域の個数,事業の発注先候補の建設会社の個数を表す.
  • 続く N 行のうちの i 行目 (1 \leqq i \leqq N) には 2 つの整数 X_{i}, Y_{i} が空白を区切りとして書かれており,i 番目の町の座標が (X_{i}, Y_{i}) であることを表す.
  • 続く M 行のうちの j 行目 (1 \leqq j \leqq M) には 4 つの整数 P_{j}, Q_{j}, R_{j}, S_{j} が空白を区切りとして書かれており,j 番目の道路を敷設できない領域を表す長方形の左下の点の座標が (P_{j}, Q_{j}) であり右上の点の座標が (R_{j}, S_{j}) であることを表す.
  • 続く C 行のうちの k 行目 (1 \leqq k \leqq C) には 2 つの整数 B_{k}, H_{k} が空白を区切りとして書かれており,k 番目の発注先候補の建設会社が国際空港を 1 つ建設するのに B_{k} のコストがかかり,最大で H_{k} 個までの国際空港を建設できることを表す.

出力

標準出力に C 行出力せよ.k 行目 (1 \leqq k \leqq C) には,k 番目の発注先候補の建設会社がこの事業を行うとしたときにかかるコストの合計値の最小値を表す 1 つの整数を出力せよ.ただし,k 番目の発注先候補の建設会社が条件を満たすように事業を行えない場合はかわりに整数 -1 を出力せよ.

制約

すべての入力データは以下の条件を満たす.

  • 1 \leqq N \leqq 200\,000.
  • 1 \leqq M \leqq 200\,000.
  • 1 \leqq C \leqq 500\,000.
  • 0 \leqq X_{i} \leqq 1\,000\,000\,000 (1 \leqq i \leqq N).
  • 0 \leqq Y_{i} \leqq 1\,000\,000\,000 (1 \leqq i \leqq N).
  • 同じ座標に 2 つ以上町があることはない.
  • 0 \leqq P_{j} < R_{j} \leqq 1\,000\,000\,000 (1 \leqq j \leqq M).
  • 0 \leqq Q_{j} < S_{j} \leqq 1\,000\,000\,000 (1 \leqq j \leqq M).
  • どの領域も,町をその長方形の内部または周上に含むことはない.
  • 1 \leqq B_{k} \leqq 1\,000\,000\,000 (1 \leqq k \leqq C).
  • 1 \leqq H_{k} \leqq N (1 \leqq k \leqq C).

小課題

小課題 1 [10 点]

以下の条件を満たす.

  • M \leqq 100.
  • C \leqq 100.

小課題 2 [30 点]

以下の条件を満たす.

  • C \leqq 100.

小課題 3 [30 点]

以下の条件を満たす.

  • M \leqq 100.

小課題 4 [30 点]

追加の制限はない.

入出力例

入力例 1

4 2 3
1 1
10 1
1 10
10 10
4 0 8 9
1 4 9 8
7 4
10 3
1 1

出力例 1

28
38
-1

この入力例を図示すると以下のようになる.太い線による長方形が道路を敷設できない領域を示している.

図

町 2 と町 4 および町 3 と町 4 を結ぶ道路を敷設することはできるが,道路を敷設できない領域と交わってしまうために町 1 と町 2 の間には道路を敷設することができない.同様に町 1 と町 3 の間にも道路を敷設することができない (道路は長方形の周とも共通部分を持ってはいけないことに注意せよ).

1 つめの建設会社は最大 4 つの国際空港を 1 つあたりコスト 7 で建設できる.この場合,道路をひとつも敷設せずにすべての町に国際空港を建設するのが最善であり,そのときのコストの合計値は 7 \times 4 = 28 となる.

2 つめの建設会社は最大 3 つの国際空港を 1 つあたりコスト 10 で建設できる.この場合,たとえば町 2 と町 4 および町 3 と町 4 を結ぶ長さ 9 の道路を敷設し,町 1 と町 2 に国際空港を建設するのが最善であり,そのときのコストの合計値は 10 \times 2 + 9 + 9 = 38 となる.

3 つめの建設会社は最大 1 つの国際空港を 1 つあたりコスト 1 で建設することができるが,町 1 が他のどの町との間にも道路を敷設できないため,問題文中の条件を満たすように事業を行うには少なくとも 2 つの国際空港を建設する必要があり,この会社は事業を行えないことがわかるので -1 を出力する.


Source Name

JOI 2012/2013 春季トレーニング合宿 Contest Day2
2 - マスコットの片付け (Mascots)

Time Limit: 2 sec / Memory Limit: 256 MiB

配点 : 100 点

問題文

JOI ちゃんは友達とマスコットで遊んでいた.楽しかった時間はあっという間に過ぎ去り,友達が帰った今は後片付けの時間である.

JOI ちゃんはマスコットを R \times C 個持っていて,片付けには縦 R 行,横 C 列のマスが並んだ長方形の領域を使う.1 個のマスには,1 個のマスコットが置かれる.上から A 行目,左から B 列目のマスのことを (A, B) と表現することにする.片付けが始まる段階で既に N 個のマスコットが置かれている.片付けを始めるときに少なくとも 1 個はマスコットが置かれていないマスがある.

JOI ちゃんはマスコットを 1 個ずつ置いて片付けをする.新しくマスコットを 1 個置いたときに,マスコットのあるマス全体が 1 個の長方形となれば,JOI ちゃんは少し幸せになる(最初の状態でマスコットのあるマス全体が 1 個の長方形になっていた場合を除く).マスコットのあるマス全体が 1 個の長方形となるとは,ある 4 つの整数 r_{1}, r_{2}, c_{1}, c_{2} (1 \leqq r_{1} \leqq r_{2} \leqq R かつ 1 \leqq c_{1} \leqq c_{2} \leqq C) が存在して,r_{1} \leqq i \leqq r_{2} かつ c_{1} \leqq j \leqq c_{2} を満たすどのマス (i, j) にもマスコットがあり,さらに他のいずれのマスにもマスコットがないことをいう.少し幸せになる回数が多ければ多いほど JOI ちゃんは今晩ぐっすり眠ることができる.

マスコットを置く際,置くマスコットの種類は区別しないものとする.少し幸せになる回数が最大となるような置き方は全部で何通りあるだろうか.

課題

マスコットを片付ける場所と既に置かれているマスコットの情報が与えられると,少し幸せになる回数が最大となるようなマスコットの置き方の個数を 1\,000\,000\,007 で割った余りを求めるプログラムを作成せよ.

入力

標準入力から以下の入力を読み込め.

  • 1 行目には整数 R,C が空白を区切りとして書かれている.R はマスコットを置く場所の行数を,C はマスコットを置く場所の列数を表す.
  • 2 行目には整数 N が書かれている.N は片付けが始まる段階で既に置かれているマスコットの個数を表す.
  • 続く N 行には,最初から置かれているマスコットの情報が書かれている.これらの行の i 行目には整数 A_{i}, B_{i} が空白を区切りとして書かれている.これはマス (A_{i}, B_{i}) に最初からマスコットが置かれていることを表す.これらの数字の組は重複しない.

出力

標準出力に,考えられる置き方の個数を 1\,000\,000\,007 で割った余りを出力せよ.

制約

すべての入力データは以下の条件を満たす.

  • 2 \leqq R \leqq 3\,000.
  • 2 \leqq C \leqq 3\,000.
  • 1 \leqq N \leqq 100\,000.

小課題

小課題 1 [10 点]

以下の条件を満たす.

  • R \leqq 3.
  • C \leqq 3.

小課題 2 [30 点]

以下の条件を満たす.

  • R \leqq 50.
  • C \leqq 50.

小課題 3 [60 点]

追加の制限はない.

入出力例

入力例 1

2 3
2
1 2
2 2

出力例 1

8

初期状態で 6 個のマスは次のようになっている(△は初期状態でマスコットが置いてあるマス).

図

6 マスのうち (1, 2) と (2, 2) には既にマスコットが置いてある.少し幸せになる回数の最大値は 2 である.少し幸せになる回数が 2 回となる配置は次の 8 通りである(数字は新しくマスコットを置く順番を表す).

1 △ 3
2 △ 4
1 △ 4
2 △ 3
2 △ 3
1 △ 4
2 △ 4
1 △ 3
3 △ 1
4 △ 2
3 △ 2
4 △ 1
4 △ 1
3 △ 2
4 △ 2
3 △ 1

8 通りの例のいずれにおいても 2 番目のマスコットを置いたときにマスコットのあるマスが 2 \times 2 の長方形に,4 番目のマスコットを置いたときにマスコットのあるマスが 2 \times 3 の長方形になり,全体で 2 回 JOI ちゃんは少し幸せになる.

入力例 2

3 3
2
1 1
3 3

出力例 2

5040

どのような順番で配置しても少し幸せになる回数は 1 回である.


Source Name

JOI 2012/2013 春季トレーニング合宿 Contest Day2
3 - スパイ (Spy)

Time Limit: 2 sec / Memory Limit: 256 MiB

配点 : 100 点

問題文

あなたは Just Odd Inventions 社を知っているだろうか?この会社の業務は「ただ奇妙な発明 (just odd inventions)」をすることである.ここでは略して JOI 社と呼ぶ.

ところで,あなたは Incredibly Odd Inventions 社を知っているだろうか?この会社の業務は「途方もなく奇妙な発明 (incredibly odd inventions)」をすることである.ここでは略して IOI 社と呼ぶ.

JOI 社と IOI 社にはそれぞれ N 人の社員がいる.JOI 社の社員は j_{1}, j_{2}, \cdot \cdot \cdot , j_{N} と名付けられており,IOI 社の社員は i_{1}, i_{2}, \cdot \cdot \cdot , i_{N} と名付けられている.また,JOI 社の社員の内の一人は JOI 社の社長であり,IOI 社の社員の内の一人は IOI 社の社長である.社長を除く社員のそれぞれに対して,その社員を直接の部下とする同じ会社の社員がちょうど一人存在する.

図

図 1: JOI 社と IOI 社の組織の例.社員を表す円から出る矢印はその社員の直接の部下を指している.

IOI 社はいつも,JOI 社の研究プロジェクトの情報を盗むことで「途方もなく奇妙な発明」をしている.いま,JOI 社では,r_{1}, r_{2}, \cdot \cdot \cdot , r_{M} と名付けられた M 個の研究プロジェクトが発足し,IOI 社では,s_{1}, s_{2}, \cdot \cdot \cdot , s_{M} と名付けられた M 個のスパイプロジェクトが発足した.IOI 社のスパイプロジェクト s_{b} は JOI 社の研究プロジェクト r_{b} の情報を盗むプロジェクトである.

プロジェクトに所属する社員の決め方は JOI 社と IOI 社で同じである.1 つのプロジェクトにつき 1 人のリーダーが決められ,リーダーはその直接の部下全員に命令を下す.命令を受け取った社員はまたその直接の部下全員に同じ命令を下す.命令を受け取った社員全てとリーダーがそのプロジェクトに所属し,その他の社員は所属しない.

プロジェクト リーダー 所属する社員
研究プロジェクト r_{1} j_{1} j_{1}, j_{2}, j_{3}
研究プロジェクト r_{2} j_{2} j_{2}, j_{3}
研究プロジェクト r_{3} j_{2} j_{2}, j_{3}
研究プロジェクト r_{4} j_{3} j_{3}
プロジェクト リーダー 所属する社員
スパイプロジェクト s_{1} i_{1} i_{1}
スパイプロジェクト s_{2} i_{1} i_{1}
スパイプロジェクト s_{3} i_{3} i_{3}
スパイプロジェクト s_{4} i_{2} i_{1}, i_{2}, i_{3}

図 2: 図 1 の JOI 社と IOI 社におけるプロジェクトの例

IOI 社の社員 i_{a} は JOI 社の社員 j_{a} から情報を盗む.スパイプロジェクト s_{b} に所属している IOI 社の社員 i_{a} は,JOI 社の社員 j_{a} が研究プロジェクト r_{b} に所属しているならばスパイ活動に成功する.それぞれの会社のすべての社員は複数のプロジェクトに所属している可能性があり,IOI 社の社員は複数のスパイプロジェクトにおいてスパイ活動に成功する可能性がある.

課題

JOI 社と IOI 社における社員の情報とプロジェクトの情報が与えられたとき,IOI 社の社員のそれぞれについて,いくつのスパイプロジェクトにおいてスパイ活動に成功するかを求めるプログラムを作成せよ.

入力

標準入力から以下の入力を読み込め.

  • 1 行目には整数 N, M が空白を区切りとして書かれており,JOI 社と IOI 社の社員がそれぞれ N 人であることと,研究プロジェクトとスパイプロジェクトがそれぞれ M 個であることを表す.
  • 続く N 行のうち,a 行目 (1 \leqq a \leqq N) には 2 つの整数 P_{a}, Q_{a} (0 \leqq P_{a} \leqq N かつ 0 \leqq Q_{a} \leqq N) が書かれており,JOI 社の社員 j_{a} が社員 j_{P_{a}} の直接の部下であり,IOI 社の社員 i_{a} が社員 i_{Q_{a}} の直接の部下であることを表す.また,P_{a} = 0 のときは社員 j_{a} は JOI 社の社長であり,Q_{a} = 0 のときは社員 i_{a} は IOI 社の社長である.
  • 続く M 行のうち,b 行目 (1 \leqq b \leqq M) には 2 つの整数 R_{b}, S_{b} (1 \leqq R_{b} \leqq N かつ 1 \leqq S_{b} \leqq N) が書かれており,研究プロジェクト r_{b} のリーダーが社員 j_{R_{b}} で,スパイプロジェクト s_{b} のリーダーが社員 i_{S_{b}} であることを表す.

出力

標準出力に N 行出力せよ.a 行目 (1 \leqq a \leqq N) には,IOI 社の社員 i_{a} がいくつのスパイプロジェクトにおいてスパイ活動に成功するかを表す 1 つの整数を出力せよ.

制約

すべての入力データは以下の条件を満たす.

  • 1 \leqq N \leqq 2\,000.
  • 1 \leqq M \leqq 500\,000.

小課題

小課題 1 [10 点]

以下の条件を満たす.

  • N \leqq 200.
  • M \leqq 200.

小課題 2 [20 点]

  • M \leqq 2\,000 を満たす.

小課題 3 [70 点]

追加の制限はない.

入出力例

入力例 1

3 4
0 2
1 0
2 2
1 1
2 1
2 3
3 2

出力例 1

1
0
2

この入出力は問題文中の例に対応している.このとき,

  • スパイプロジェクト s_{1}, s_{2}, s_{4} に所属する社員 i_{1} は,社員 j_{1} が研究プロジェクト r_{1} に属するため,スパイプロジェクト s_{1} においてスパイ活動に成功する.
  • スパイプロジェクト s_{4} に属する社員 i_{2} は,社員 j_{2} が研究プロジェクト r_{4} に属さないため,どのスパイプロジェクトにおいてもスパイ活動に成功しない.
  • スパイプロジェクト s_{3}, s_{4} に属する社員 i_{3} は,社員 j_{3} が研究プロジェクト r_{3}, r_{4} に属するため,スパイプロジェクト s_{3}, s_{4} においてスパイ活動に成功する.

Source Name

JOI 2012/2013 春季トレーニング合宿 Contest Day2