928 . 貓咪國防禦計劃

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Fysty

User's AC Ratio

88.9% (8/9)

Submission's AC Ratio

36.7% (18/49)

Tags

ioicamp ioicamp-2025

Description

貓咪國是一個人與貓和平相處的國度，人類養活貓咪，貓咪治癒人類，真是烏托邦一般的世界。但貓咪國跟鄰國汪汪國的關係不太好，兩國時常爭吵並開戰，而現在正是兩國開戰的時刻。

貓咪國有 $n$ 個城市，雖然有完善系統的「喵喵車」可以讓人們在兩個城市之間移動，但在戰爭時間搭乘喵喵車容易被汪汪國的砲車鎖定而造成危險，戰爭期間喵喵車不會開放，取代而之的是數條雙向通行的公路讓貓咪國的人們依然可以在戰爭時間在城市之間移動。詳細來說：

  • 對所有 $1 < i \leq n$，第 $i$ 個城市與第 $i - 1$ 個城市連接著一條公路。
  • 對所有 $1 \leq i \leq \lfloor n / 2 \rfloor$，第 $i$ 個城市與第 $n + 1 - i$ 個城市連接著一條公路。

然而好景不常，戰爭開打一段時間後汪汪國已經佔領了貓咪國的一些城市。為了了解現在的戰況，貓咪國的首領想要知道在不經過已被汪汪國佔領的城市的情況下，從第 $u_i$ 個城市到第 $v_i$ 個城市最少需要經過幾條公路。由於戰況緊急，他希望知道 $q$ 個形如上述問題的答案，你能幫幫他嗎？

Input Format

輸入第一行有兩個正整數 $n, q$，代表貓咪國的城市數量與問題的數量。

輸入第二行有一個長度為 $n$ 的 01 字串 $s$，若 $s_i = 1$ 則代表第 $i$ 個城市被汪汪國佔領了，否則代表沒有。

接下來 $q$ 行第 $i$ 行有兩個正整數 $u_i, v_i$，代表貓咪國的首領想要知道從城市 $u_i$ 走到城市 $v_i$ 最少需要經過幾條公路。

  • $1 \leq n, q \leq 2 \times 10^ 5$
  • $|s| = n$
  • $s_i \in \lbrace 0, 1 \rbrace$
  • $1 \leq u_i, v_i \leq n$
  • $s_{u_i} = 0, s_{v_i} = 0$

Output Format

請輸出 $q$ 行，若從城市 $u_i$ 無法在不經過被汪汪國佔領的城市的情況下到達城市 $v_i$，請在第 $i$ 行輸出 -1，否則請在第 $i$ 行輸出最少需要經過幾條公路。

Sample Input 1

12 6
010010001000
1 4
1 12
7 7
6 4
3 11
12 4

Sample Output 1

5
1
0
-1
2
4

Sample Input 2

20 10
00101000100001000001
12 4
8 19
1 7
7 12
12 15
4 19
19 1
18 8
2 11
10 7

Sample Output 2

8
7
8
3
5
3
2
6
11
5

Hints

在第一筆範測中，以下為第一個問題的最優路線：

  • $1 \to 12 \to 11 \to 10 \to 3 \to 4$

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~20 保證被汪汪國佔領的城市數量不超過 $100$ 30
3 0~45 無額外限制 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 1048576 65536 1 2 3
1 2000 1048576 65536 1 2 3
2 2000 1048576 65536 2 3
3 2000 1048576 65536 2 3
4 2000 1048576 65536 2 3
5 2000 1048576 65536 2 3
6 2000 1048576 65536 2 3
7 2000 1048576 65536 2 3
8 2000 1048576 65536 2 3
9 2000 1048576 65536 2 3
10 2000 1048576 65536 2 3
11 2000 1048576 65536 2 3
12 2000 1048576 65536 2 3
13 2000 1048576 65536 2 3
14 2000 1048576 65536 2 3
15 2000 1048576 65536 2 3
16 2000 1048576 65536 2 3
17 2000 1048576 65536 2 3
18 2000 1048576 65536 2 3
19 2000 1048576 65536 2 3
20 2000 1048576 65536 2 3
21 2000 1048576 65536 3
22 2000 1048576 65536 3
23 2000 1048576 65536 3
24 2000 1048576 65536 3
25 2000 1048576 65536 3
26 2000 1048576 65536 3
27 2000 1048576 65536 3
28 2000 1048576 65536 3
29 2000 1048576 65536 3
30 2000 1048576 65536 3
31 2000 1048576 65536 3
32 2000 1048576 65536 3
33 2000 1048576 65536 3
34 2000 1048576 65536 3
35 2000 1048576 65536 3
36 2000 1048576 65536 3
37 2000 1048576 65536 3
38 2000 1048576 65536 3
39 2000 1048576 65536 3
40 2000 1048576 65536 3
41 2000 1048576 65536 3
42 2000 1048576 65536 3
43 2000 1048576 65536 3
44 2000 1048576 65536 3
45 2000 1048576 65536 3
Submit
Back to Top