SPyofgame's blog

By SPyofgame, history, 4 years ago, In English

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
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

This is a not an ongoing contest problem but if you mind it you can ignore my blog. Thanks for reading