link — http://mirror.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://mirror.codeforces.com/contest/791/submission/25610369 AC link — http://mirror.codeforces.com/contest/791/submission/25625604
Thanks in advance!
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)
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.