修正 C++ 的程式碼在使用一定量動態記憶體後會產生 RF 的問題 @ 2019/12/6 4:45pm
Submit Ranklist
Problem : 258 - Flood
Special Judge
Problem Statistics
Solved Member: 9 Submission: 42 User Tried: 10Statement:
在1964年的洪水侵襲札格拉布(Zagreb)這座城市後造成了許多的災難。許多的建築物在洪水襲擊牆壁後被完全地摧毀。
在本題中，給定一個這個城市在洪水侵襲前的簡化模型，請找出哪些牆壁在洪水侵襲之後將仍然保持完整無缺。
這個模型包括了N個在座標平面上的點與W個牆壁，其中每一個牆壁連接兩個點並且中間不會通過任何其它的點。這個模型有下列的特性:
•兩個牆壁不會相交或是重疊，但他們可能在端點處相接。
•每一個牆壁都是與水平軸平行或是與垂直軸平行。
在剛開始時，整個座標平面是乾的。在時間0時，洪水瞬間地淹沒最外圍(沒有牆壁包圍的空間)。在正好一個小時後，每個牆壁若有一側是水而另一側是空氣的話，就會因水壓的關係而毀壞，洪水然後會淹沒任何沒有被牆壁完整包圍的新區域。這時，將又會有新的牆壁一側是水而另一側是空氣，再經過另一個小時後，這些牆壁也會毀壞而洪水繼續氾濫。這個過程將持續直到洪水淹沒整個區域為止。
下圖是整個過程的一個例子。
在本題中，給定一個這個城市在洪水侵襲前的簡化模型，請找出哪些牆壁在洪水侵襲之後將仍然保持完整無缺。
這個模型包括了N個在座標平面上的點與W個牆壁，其中每一個牆壁連接兩個點並且中間不會通過任何其它的點。這個模型有下列的特性:
•兩個牆壁不會相交或是重疊，但他們可能在端點處相接。
•每一個牆壁都是與水平軸平行或是與垂直軸平行。
在剛開始時，整個座標平面是乾的。在時間0時，洪水瞬間地淹沒最外圍(沒有牆壁包圍的空間)。在正好一個小時後，每個牆壁若有一側是水而另一側是空氣的話，就會因水壓的關係而毀壞，洪水然後會淹沒任何沒有被牆壁完整包圍的新區域。這時，將又會有新的牆壁一側是水而另一側是空氣，再經過另一個小時後，這些牆壁也會毀壞而洪水繼續氾濫。這個過程將持續直到洪水淹沒整個區域為止。
下圖是整個過程的一個例子。
Task:
寫一個程式，當給定N個點的座標與連接這些點的W個牆壁的描述後，找出哪些牆壁可在洪水侵襲之後依然可以保持挺立。
Input:Output:
輸入的第一行有一個整數N (2 ≤ N ≤ 100 000)，代表在平面上點的數目。
接下來N行的每一行都有兩個整數X和Y(兩者都介於0和1,000,000間，包括0與1,000,000)，表示每一點的座標值。這些點將依照它們被給定的順序編號1到N。沒有任何兩點會座落在相同座標。
接下來的一行有一個整數W (1 ≤ W ≤ 2N)，是表示牆壁的數目。
接下來W行的每一行都有兩個不同的整數A和B (1 ≤ W ≤ 2N)，表示在洪水來犯前有一個牆壁連接A與B兩點。這些牆壁將依照它們被給定的順序編號1到W。
接下來N行的每一行都有兩個整數X和Y(兩者都介於0和1,000,000間，包括0與1,000,000)，表示每一點的座標值。這些點將依照它們被給定的順序編號1到N。沒有任何兩點會座落在相同座標。
接下來的一行有一個整數W (1 ≤ W ≤ 2N)，是表示牆壁的數目。
接下來W行的每一行都有兩個不同的整數A和B (1 ≤ W ≤ 2N)，表示在洪水來犯前有一個牆壁連接A與B兩點。這些牆壁將依照它們被給定的順序編號1到W。
輸出的第一行應該有一個整數K，代表在洪水過後仍然保持挺立牆壁的數目。
接下來的K行應該列出那些還依然挺立牆壁的編號，每行一個牆壁。這些牆壁可以以任何順序輸出。
接下來的K行應該列出那些還依然挺立牆壁的編號，每行一個牆壁。這些牆壁可以以任何順序輸出。
Sample Input:Sample Output:
15
1 1
8 1
4 2
7 2
2 3
4 3
6 3
2 5
4 5
6 5
4 6
7 6
1 8
4 8
8 8
17
1 2
2 15
15 14
14 13
13 1
14 11
11 12
12 4
4 3
3 6
6 5
5 8
8 9
9 11
9 10
10 7
7 6
1 1
8 1
4 2
7 2
2 3
4 3
6 3
2 5
4 5
6 5
4 6
7 6
1 8
4 8
8 8
17
1 2
2 15
15 14
14 13
13 1
14 11
11 12
12 4
4 3
3 6
6 5
5 8
8 9
9 11
9 10
10 7
7 6
4
6
15
16
17
6
15
16
17
HINT:
範例與圖片對應。
Source:
IOI 2007Problem Setter
hanhan0912Testdata:
| Test | Time | Memory | Score |
|---|---|---|---|
| 0 | 2000ms | 32768kb | |
| 1 | 2000ms | 32768kb | 8 |
| 2-1 | 2000ms | 32768kb | 8 |
| 2-2 | 2000ms | 32768kb | |
| 2-3 | 2000ms | 32768kb | |
| 3 | 2000ms | 32768kb | 8 |
| 4-1 | 2000ms | 32768kb | 8 |
| 4-2 | 2000ms | 32768kb | |
| 5-1 | 2000ms | 32768kb | 8 |
| 5-2 | 2000ms | 32768kb | |
| 6 | 2000ms | 32768kb | 3 |
| 7 | 2000ms | 32768kb | 4 |
| 8-1 | 2000ms | 32768kb | 4 |
| 8-2 | 2000ms | 32768kb | |
| 9-1 | 2000ms | 32768kb | 4 |
| 9-2 | 2000ms | 32768kb | |
| 10 | 2000ms | 32768kb | 9 |
| 11 | 2000ms | 32768kb | 9 |
| 12-1 | 2000ms | 32768kb | 9 |
| 12-2 | 2000ms | 32768kb | |
| 13-1 | 2000ms | 32768kb | 9 |
| 13-2 | 2000ms | 32768kb | |
| 14-1 | 2000ms | 32768kb | 9 |
| 14-2 | 2000ms | 32768kb |
NeoHOJ — The new era of HOJ
頁面讀取時間: 0.0131 秒，使用記憶體: 0.46MB 。
GitHub