According to the 1327B's solution, O(n+m) is taken.
But i don't think that. In this situation,
N = 100'000 1st princess can marry 1 2 3 4 ... 100'000 2nd princess can marry 1 2 3 4 .., 100'000 . . . 100'000th princess can marry 1 2 3 4 .. 100'000
Total time complexity will be O(N^2), if i understood that solution correct.
Can you help me?
Blog comments
In attempt to improve the asking-for-help blogs here in CF, I'll start with a summary of good and bad points of your blog.
Good:
Stated the question clearly and provided an example
Reasonable English, formatting and politeness
Bad:
You should link the problem and editorial instead of just giving its code
Ideally give a summary of the solution as you understand it. This will save time and also make it clear if you misunderstood some part of the solution.
Actual help
In the editorial $$$m$$$ indicates the total number of kingdoms across all lists. In your example case you would have $$$n$$$ lists of $$$n$$$ kingdoms so a test of size $$$n^2$$$ — which is not allowed. You can see the constraints say that the total number of kingdoms in all lists across all tests is at most $$$10^5$$$, while $$$n^2$$$ in your test would be $$$10^{10}$$$.
So if your example were valid, it would indeed be $$$O(n^2)$$$, but we would also have $$$m=n^2$$$ and so $$$O(n+m)=O(n+n^2)=O(n^2)$$$ would be the same thing. The claim that it is $$$O(n+m)$$$ is indeed correct.
Thank you for your comments and I will keep in mind your comments.
I had misunderstood that constraints "the total number of kingdoms in all lists across all tests is at most 10^5"
Thank you very much.
By the way, you should press the "Reply" button with underline to reply someone so that he/she can get a notification of your reply.