tril0713's blog

Time limit exceeeeeeeeeeed on problem E2
By tril0713, history, 2 months ago, In English

My solution: each bit is independent so let us consider them separately.

Now notice that if the first row and colmn are already filled, the whole grid is uniquely determined.

Use a dsu to maintain the equality relationship between the positions and the final time complexity is $$$\mathcal O((n + q) \log V \alpha n)$$$.

I have tested the code in mashups and it runs 2499ms, which means that the constant is too big. Can any one help me to optimize the code?

Code
  • Vote: I like it
  • +20
  • Vote: I do not like it

»
2 months ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

z = (oz >> i) & 1;
Instead of maintaining $$$\log V$$$ DSU, you can maintain just 1 DSU and maintain z as 30-bit integer instead of 1-bit integer.

285717430

→ Reply