206 . 三點共線

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

33.3% (1/3)

Submission's AC Ratio

20.0% (2/10)

Tags

ioicamp ioicamp-2021

Description

給一個連通簡單無向圖，點的編號 \(1, 2, \ldots, N\)。

每次詢問三個點 \(a,b,c\)，問是否存在一條簡單路徑同時包含 \(a,b,c\)，三個點在路徑上不必照順序。

Input Format

第一行是 $N,M,Q$，分別代表頂點數、邊數和詢問數。

接下來有 $M$ 行每行有兩個整數 $u,v$ 代表兩點之間有一條無向邊。

接下來 $Q$ 行每行有三個整數 $a,b,c$ 代表要詢問是否在同一條路徑上的三點。

  • $1\le N,M,Q\le 300000$
  • $1\le u,v,a,b,c\le N$
  • 保證給定的圖為簡單連通圖

Output Format

如果三點在同一條路徑上，輸出 Yes，否則輸出 No。

Sample Input 1

6 5 3
1 2
2 3
2 4
4 5
2 6
1 2 3
1 3 6
1 4 5

Sample Output 1

Yes
No
Yes

Sample Input 2

8 9 4
1 2
2 3
3 1
4 5
5 6
6 4
6 7
7 1
1 8
1 2 8
1 6 8
3 5 8
3 7 5

Sample Output 2

Yes
Yes
No
Yes

Hints

Problem Source

IOICamp 2021 Day2 pF

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~28 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 1048576 65536 1 2
1 3000 1048576 65536 1 2
2 3000 1048576 65536 2
3 3000 1048576 65536 2
4 3000 1048576 65536 2
5 3000 1048576 65536 2
6 3000 1048576 65536 2
7 3000 1048576 65536 2
8 3000 1048576 65536 2
9 3000 1048576 65536 2
10 3000 1048576 65536 2
11 3000 1048576 65536 2
12 3000 1048576 65536 2
13 3000 1048576 65536 2
14 3000 1048576 65536 2
15 3000 1048576 65536 2
16 3000 1048576 65536 2
17 3000 1048576 65536 2
18 3000 1048576 65536 2
19 3000 1048576 65536 2
20 3000 1048576 65536 2
21 3000 1048576 65536 2
22 3000 1048576 65536 2
23 3000 1048576 65536 2
24 3000 1048576 65536 2
25 3000 1048576 65536 2
26 3000 1048576 65536 2
27 3000 1048576 65536 2
28 3000 1048576 65536 2
Submit
Back to Top