PeterParker's blog

Codeforces Round #405 — Div 2 : Problem B — regarding use of long long
By PeterParker, history, 7 years ago, In English

link — http://codeforces.com/contest/791/problem/B

I used the fact that each in each connected component there should be an edge between each pair of vertices. Hence the number of edges given should be equal to — summation x*(x-1)/2 for each connected component, where x = size of the connected component.

I used int and got a WA and when I replaced it with long long it got Accepted. Now my question is if the answer has to be "YES

" then sum should be <= 150000 (since that is the range of M in the question) so int should suffice then why did I get a WA?

WA link — http://codeforces.com/contest/791/submission/25610369 AC link — http://codeforces.com/contest/791/submission/25625604

Thanks in advance!

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

int sz = 150000; sz*(sz-1) > INT_MAX So you need either declare sz as int64_t, or cast before the multiplication: (long long)sz * (sz-1)

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

We can say that if answer for specified input is "YES", than overflow is impossible.
However, if answer is "NO", than component size can be big enough to cause overflow.

→ Reply