Asking for a graph problem

Правка en8, от SPyofgame, 2020-04-01 13:30:15

Given two number n and q where 1 ≤ n, q ≤ 10.000

There are n nodes, each node have a green string connect to another. Each 2 node only have 1 string connect between them. There are n * (n — 1) * (n — 2) / 6 total string

You have to answer q queries, each query give 2 number u and v. You paint the string connect (u, v) by color red if they are green, and green if they are red (red <-> green). Then you have to count the number of triangle ABC (1 ≤ A, B, C ≤ n) where (A, B), (B, C), (C, A) have same color (all are red or green).

Time limit for the problem is 1s

Memory limit for the problem is 256Mb

Here are examples

Example 1
Example 2
Example 3

Notice that the number of valid triangle can be bigger than 10 ^ 9

I think the problem can be solved using map

My brute-force approach give 50% points
Update: Solution
Теги #graph, #counting, #asking

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский SPyofgame 2020-04-01 13:30:15 21
en7 Английский SPyofgame 2020-04-01 13:25:31 30
en6 Английский SPyofgame 2020-04-01 13:20:04 5 Tiny change: '<< endl;\n }\n\n r' -> '<< endl;\n }\n\n r'
en5 Английский SPyofgame 2020-04-01 13:19:35 52
en4 Английский SPyofgame 2020-04-01 13:18:26 1235
en3 Английский SPyofgame 2020-03-31 12:50:49 8
en2 Английский SPyofgame 2020-03-31 12:49:59 4
en1 Английский SPyofgame 2020-03-31 12:49:43 2947 Initial revision (published)