22517번 - Box Witch 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 512 MB | 15 | 5 | 5 | 45.455% |
문제
ハコの魔女 H.N.ELLY はとある動画サイトの熱狂的なファンである．ハコの魔女の強さはその時々のその動画サイトからの転送速度に応じて変化するのではないかと美樹さやかは考えた．そこで動画サイトからハコの魔女の持つコンピュータまでの過去の転送速度 (=単位時間あたりのデータの転送量) を調べたい．
初期のインターネットのネットワークの構造とそれ以降のネットワークの構造の変化を表すクエリが与えられるので，各変化について変化した直後の動画サイトからハコの魔女の持つコンピュータまでの転送速度を求めよ．
インターネットは複数の転送装置からなるものと見なし，各々をつなぐ回線は双方向に情報を送ることができ，その転送速度の最大は 1 であるとする．また，ネットワークは常に動画サイトからハコの魔女へ送られるデータの転送速度を最大化するように運ぶものとする．
입력
入力は以下の形式で与えられる．
N E Q F1 T1 F2 T2 … FE TE M1 A1 B1 M2 A2 B2 … MQ AQ BQ
N は動画サイトとハコの魔女の持つコンピュータを含めた転送装置の数である．番号が 1 である転送装置は動画サイトであり，番号が N である転送装置はハコの魔女の持つコンピュータである．E は初期状態で接続されている転送装置の組み合わせの数であり，Q はインターネットが変化した回数である．初期のインターネットは Fi と Ti が転送速度 1 で双方向に接続されていることを表す．
ネットワークの変化は時系列順に与えられ，j 番目の変化は Mj が 1 であれば Aj, Bj 間がつながれたことを表し，Mj が 2 であれば Aj, Bj 間の接続が切れたことを表す．
출력
各変化の直後における，動画サイトからハコの魔女の持つコンピュータまでの転送速度を出力せよ．
제한
- 2≤N≤500
- 0≤E≤20,000
- 1≤Q≤1,000
- 1≤Fi≤N, 1≤Ti≤N, Fi≠Ti (1≤i≤E)
- すべての {Fi,Ti} のペアは異なる．
- 1≤Mj≤2, 1≤Aj≤N , 1≤Bj≤N , Aj≠Bj(1≤j≤Q)
- ネットワークのどの段階においても次のことが成り立つ : どの 2 つの転送装置の間も高々 1 つの回線でしか繋がれていない．
- 2 つの転送装置の間が既に繋がれている状態でそれらの間を接続するようなクエリが来たり，2 つの転送装置の間が回線で繋がれていない状態でそれらの間の接続を切るようなクエリが来ることはない．
예제 입력 1
2 1 2 1 2 2 1 2 1 2 1
예제 출력 1
0 1
最初の変化の後，ハコの魔女のコンピュータと動画サイトは繋がらなくなっているので転送速度は 0 である．
2 度目の変化の後は両者は直接繋がっており，転送速度は 1 になる．
예제 입력 2
3 0 4 1 2 3 1 2 1 1 3 1 2 2 3
예제 출력 2
0 1 2 1
예제 입력 3
6 4 8 1 2 1 3 4 6 5 6 1 2 4 1 3 5 1 2 5 1 3 4 2 2 4 2 3 5 1 2 4 2 2 1
예제 출력 3
1 2 2 2 2 2 2 1
예제 입력 4
12 38 6 1 2 1 3 1 4 1 5 2 3 2 4 2 5 2 6 2 7 2 8 2 12 3 4 3 5 3 6 3 7 3 8 4 5 4 6 4 7 4 8 5 6 5 7 5 8 6 7 6 8 6 9 6 10 6 12 7 8 7 9 7 10 8 9 8 10 9 10 9 11 9 12 10 11 11 12 2 6 12 2 9 12 1 9 12 1 6 12 2 6 12 1 6 12
예제 출력 4
3 2 3 4 3 4