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 commentsIn 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 helpIn 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.