tranducbo's blog

How to better utilize memory for minimum spanning trees problems?
By tranducbo, history, 15 months ago, In English

I've been trying to solve 1857G - Counting Graphs for a while and it seems that my solutions will invariably receive MLE. Is there any way to use less memory to solve these kinds of problems. Any help would be appreciated.

My solutions: 220733247

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
15 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Your code gets mle because of int overflow. Changing to this gets AC.

ans = ans * bipow(S - e.c + 1, (long long)sz[find(e.u)] * sz[find(e.v)] - 1) % mod;

C++ is weird sometimes. I saw that there is no chance this can get mle if there is no rte. Signed/unsigned overflow is usually when this kind of weird stuff happens.

→ Reply