Asking for a graph problem

Revision en4, by SPyofgame, 2020-04-01 13:18:26

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
Tags #graph, #counting, #asking

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English SPyofgame 2020-04-01 13:30:15 21
en7 English SPyofgame 2020-04-01 13:25:31 30
en6 English SPyofgame 2020-04-01 13:20:04 5 Tiny change: '<< endl;\n }\n\n r' -> '<< endl;\n }\n\n r'
en5 English SPyofgame 2020-04-01 13:19:35 52
en4 English SPyofgame 2020-04-01 13:18:26 1235
en3 English SPyofgame 2020-03-31 12:50:49 8
en2 English SPyofgame 2020-03-31 12:49:59 4
en1 English SPyofgame 2020-03-31 12:49:43 2947 Initial revision (published)