8 . 無鹿可退

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

wiwiho

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

23.1% (3/13)

Tags

ntucpc-challenge1

Description


鹿乃子乃子跳下懸崖躲避獵友會的追捕

不只是鹿乃子乃子，其他生活在大自然的鹿隻也會遇到遭到獵捕的危機。近期即將又要有大批獵人前來，鹿群打算趕緊修葺緊急通道，以避免無鹿可退的窘境。

鹿群的棲息地由 $N$ 個據點而成，在據點之間一共有 $M$ 個可以建造緊急通道的預定地，第 $i$ 個緊急通道連通據點 $u_i, v_i$，能讓鹿隻在兩據點之間移動，並且在 $M$ 條緊急通道皆完工的情況下，能確保從任何一個據點開始皆可以透過若干條緊急通道撤離到其他所有的據點。另外，兩個據點之間可能會有多個緊急通道的預定地。

每一天鹿群可以建造至多一條緊急通道，然而明天跟意外永遠不知道何者會先到來，在建造緊急通道的過程中也有可能遭到獵人的追擊。幸好根據法律規定，獵人也不能每天打獵，鹿群已經提前得知了每一個緊急通道的預定地皆會有一段時間——第 $s_i$ 天到第 $t_i$ 天（包含 $s_i, t_i$）獵人是絕對不會出現的。鹿群評估工程風險的方式很簡單，如果在施工的當天該預定地獵人絕對不會出現，則該工程的風險值為 $0$；否則，該工程的風險值為 $1$。

在第一階段的工程中，鹿群希望先建造一些緊急通道使獨從任何一個據點開始皆可以透過若干條緊急通道撤離到其他所有的據點。請你寫一支程式幫鹿群安排施工的日程，最小化完成第一階段工程需要遭遇的風險值總和。

Input Format

輸入的第一行包含兩個整數 $N, M$。接下來 $M$ 行，每行包含四個整數 $u_i, v_i, s_i, t_i$，表示第 $i$ 個緊急通道預定地的工程資訊。

  • $2 \le N \le 1000$
  • $N-1 \le M \le 2000$
  • $1 \le u_i, v_i \le N$
  • $u_i \ne v_i$
  • $1 \le s_i \le t_i \le 10^ 9$
  • 保證在建造了全部的緊急通道後，從任何一個據點開始皆可以透過若干條緊急通道撤離到其他所有的據點

Output Format

第一行請輸出一個整數，表示要完成第一階段工程至少需要遭遇的風險值總和。第二行請輸出一個長度為 $M$ 的 01 字串，若要在風險值為 $0$ 的狀態下建造第 $i$ 條緊急通道，則第 $i$ 個字元為 1；否則，第 $i$ 個字元為 $0$。

如果有多種可能的輸出，你可以輸出任意一種。

Sample Input 1

5 7
1 2 1 1
2 3 2 2
3 4 3 3
1 3 1 1
2 4 3 3
1 4 4 4
4 5 2 2

Sample Output 1

0
1010011

Sample Input 2

5 10
5 2 1 2
1 4 1 1
1 5 3 3
3 4 1 2
3 1 1 2
5 3 2 3
4 2 2 2
2 1 1 2
2 3 2 2
5 2 1 2

Sample Output 2

1
1110000000

Hints

第一筆範例測資中，鹿群可以在第 $1$ 天建造第 $1$ 條緊急通道，在第 $2$ 天建造第 $7$ 條緊急通道，在第 $3$ 天建造第 $3$ 條緊急通道，在第 $4$ 天建造第 $6$ 條緊急通道。四條緊急通道皆在風險值為 $0$ 的狀態下建造完，並且建造完後即完成第一階段工程的目標。

第二筆範例測資中，鹿群可以在第 $1$ 天建造第 $2$ 條緊急通道，在第 $2$ 天建造第 $1$ 條緊急通道，在第 $3$ 天建造第 $3$ 條緊急通道，在第 $4$ 天建造第 $4$ 條緊急通道。建造第 $4$ 條緊急通道時風險值為 $1$，其餘則為 $0$。

Problem Source

改編自 IOICamp 2024 Day 4 pF - 又是城市規劃

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~15 $\forall 1 \leq i \leq M,\ s_i=t_i=i$ 0.48763
3 16~53 $M=N-1$，$\forall 1 \leq i < M,\ u_i=i,\ v_i=i+1$ 0.51237
4 54~61 $N \leq 50, M \leq 100$ 4
5 54~72 $N \leq 200, M \leq 1000$ 1
6 9~15, 35~96 $N \leq 400, M \leq 1000$ 4
7 0~120 無額外限制 90

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 262144 65536 1 7
1 5000 262144 65536 1 7
2 5000 262144 65536 2 7
3 5000 262144 65536 2 7
4 5000 262144 65536 2 7
5 5000 262144 65536 2 7
6 5000 262144 65536 2 7
7 5000 262144 65536 2 7
8 5000 262144 65536 2 7
9 5000 262144 65536 2 6 7
10 5000 262144 65536 2 6 7
11 5000 262144 65536 2 6 7
12 5000 262144 65536 2 6 7
13 5000 262144 65536 2 6 7
14 5000 262144 65536 2 6 7
15 5000 262144 65536 2 6 7
16 5000 262144 65536 3 7
17 5000 262144 65536 3 7
18 5000 262144 65536 3 7
19 5000 262144 65536 3 7
20 5000 262144 65536 3 7
21 5000 262144 65536 3 7
22 5000 262144 65536 3 7
23 5000 262144 65536 3 7
24 5000 262144 65536 3 7
25 5000 262144 65536 3 7
26 5000 262144 65536 3 7
27 5000 262144 65536 3 7
28 5000 262144 65536 3 7
29 5000 262144 65536 3 7
30 5000 262144 65536 3 7
31 5000 262144 65536 3 7
32 5000 262144 65536 3 7
33 5000 262144 65536 3 7
34 5000 262144 65536 3 7
35 5000 262144 65536 3 6 7
36 5000 262144 65536 3 6 7
37 5000 262144 65536 3 6 7
38 5000 262144 65536 3 6 7
39 5000 262144 65536 3 6 7
40 5000 262144 65536 3 6 7
41 5000 262144 65536 3 6 7
42 5000 262144 65536 3 6 7
43 5000 262144 65536 3 6 7
44 5000 262144 65536 3 6 7
45 5000 262144 65536 3 6 7
46 5000 262144 65536 3 6 7
47 5000 262144 65536 3 6 7
48 5000 262144 65536 3 6 7
49 5000 262144 65536 3 6 7
50 5000 262144 65536 3 6 7
51 5000 262144 65536 3 6 7
52 5000 262144 65536 3 6 7
53 5000 262144 65536 3 6 7
54 5000 262144 65536 4 5 6 7
55 5000 262144 65536 4 5 6 7
56 5000 262144 65536 4 5 6 7
57 5000 262144 65536 4 5 6 7
58 5000 262144 65536 4 5 6 7
59 5000 262144 65536 4 5 6 7
60 5000 262144 65536 4 5 6 7
61 5000 262144 65536 4 5 6 7
62 5000 262144 65536 5 6 7
63 5000 262144 65536 5 6 7
64 5000 262144 65536 5 6 7
65 5000 262144 65536 5 6 7
66 5000 262144 65536 5 6 7
67 5000 262144 65536 5 6 7
68 5000 262144 65536 5 6 7
69 5000 262144 65536 5 6 7
70 5000 262144 65536 5 6 7
71 5000 262144 65536 5 6 7
72 5000 262144 65536 5 6 7
73 5000 262144 65536 6 7
74 5000 262144 65536 6 7
75 5000 262144 65536 6 7
76 5000 262144 65536 6 7
77 5000 262144 65536 6 7
78 5000 262144 65536 6 7
79 5000 262144 65536 6 7
80 5000 262144 65536 6 7
81 5000 262144 65536 6 7
82 5000 262144 65536 6 7
83 5000 262144 65536 6 7
84 5000 262144 65536 6 7
85 5000 262144 65536 6 7
86 5000 262144 65536 6 7
87 5000 262144 65536 6 7
88 5000 262144 65536 6 7
89 5000 262144 65536 6 7
90 5000 262144 65536 6 7
91 5000 262144 65536 6 7
92 5000 262144 65536 6 7
93 5000 262144 65536 6 7
94 5000 262144 65536 6 7
95 5000 262144 65536 6 7
96 5000 262144 65536 6 7
97 5000 262144 65536 7
98 5000 262144 65536 7
99 5000 262144 65536 7
100 5000 262144 65536 7
101 5000 262144 65536 7
102 5000 262144 65536 7
103 5000 262144 65536 7
104 5000 262144 65536 7
105 5000 262144 65536 7
106 5000 262144 65536 7
107 5000 262144 65536 7
108 5000 262144 65536 7
109 5000 262144 65536 7
110 5000 262144 65536 7
111 5000 262144 65536 7
112 5000 262144 65536 7
113 5000 262144 65536 7
114 5000 262144 65536 7
115 5000 262144 65536 7
116 5000 262144 65536 7
117 5000 262144 65536 7
118 5000 262144 65536 7
119 5000 262144 65536 7
120 5000 262144 65536 7
Submit
Back to Top