DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

Starry Sky Parade

Back to problem

Editorial

The last added vertex was connected either to every previous vertex or to none of them. Therefore, when SSS vertices remain, we can remove a vertex of degree S−1S-1S−1 or degree 000. Repeating this until one vertex remains reconstructs the insertion order and the operation used for every inserted vertex in reverse.

We can implement the removal process efficiently. Let DvD_vDv​ be the degree of vertex vvv in the original graph, and let CCC be the number of removed universal vertices. Every removed universal vertex was adjacent to every vertex that still remains, while every removed isolated vertex was adjacent to none of them. Thus, the current degree of every remaining vertex vvv is

Dv−C.D_v-C.Dv​−C.

When SSS vertices remain, we may remove either of the following.

  • A vertex with Dv=CD_v=CDv​=C is currently isolated.
  • A vertex with Dv=C+S−1D_v=C+S-1Dv​=C is currently universal.

Place the vertices into buckets by their original degrees. The required vertex can then be removed in O(1)O(1)O(1) per step. One of the two kinds is always available because every input satisfies the condition. Including the computation of the initial degrees, reconstruction takes O(N+M)O(N+M)O(N+M) time.

Now follow the removal history in reverse and assign brightnesses. Give the first vertex brightness

⌈N2⌉.\left\lceil\frac N2\right\rceil.⌈2N​⌉.

Let LLL and RRR be the minimum and maximum brightness assigned so far.

  • For an isolated vertex, assign N−RN-RN−R. Its sum with every existing brightness is at most NNN, so it creates no edge.
  • For a universal vertex, assign N−L+1N-L+1N−L+1. Its sum with every existing brightness is greater than NNN, so it is connected to every existing vertex.

It remains to show that every brightness lies between 111 and NNN. The invariant

L+R∈{N,N+1}L+R\in\{N,N+1\}L+R∈{N,N+1}

holds after every step. Also, adding one vertex increases R−LR-LR−L by at most one, so R−L≤N−1R-L\leq N-1R−L≤N−1 throughout the construction. Together, these properties imply L≥1L\geq1L≥ and .

The time complexity is O(N+M)O(N+M)O(N+M), and the space complexity is also O(N+M)O(N+M)O(N+M).

Solution written by GPT6

+
S−
1
1
R≤NR\leq NR≤N