DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

Starry Sky Parade

返回题目

题解

마지막에 추가된 별은 기존 모든 별과 연결되었거나 어느 별과도 연결되지 않았다. 따라서 현재 남아 있는 정점이 SSS개라면 차수가 S−1S-1S−1인 정점 또는 차수가 000인 정점을 하나 제거할 수 있다. 이를 정점 하나만 남을 때까지 반복하면 정점이 추가된 순서와 각 정점이 추가될 때 사용한 방법을 역순으로 복원할 수 있다.

이 제거 과정을 빠르게 구현해 보자. 처음 그래프에서의 정점 vvv의 차수를 DvD_vDv​라 하고, 지금까지 제거한 연결 정점의 개수를 CCC라 하자. 제거된 연결 정점은 현재 남아 있는 모든 정점과 인접했고, 제거된 고립 정점은 현재 남아 있는 어떤 정점과도 인접하지 않았다. 따라서 아직 남은 정점 vvv의 현재 차수는 항상

Dv−CD_v-CDv​−C

이다.

현재 정점이 SSS개 남았다면 다음 정점을 제거할 수 있다.

  • Dv=CD_v=CDv​=C인 정점은 현재 차수가 000인 고립 정점이다.
  • Dv=C+S−1D_v=C+S-1Dv인 정점은 현재 차수가 인 연결 정점이다.

초기 차수별로 정점을 버킷에 넣으면 매 단계에서 필요한 정점을 O(1)O(1)O(1)에 꺼낼 수 있다. 입력이 조건을 만족하므로 둘 중 하나는 항상 존재한다. 간선을 읽어 초기 차수를 계산하는 시간을 포함하여 복원에는 O(N+M)O(N+M)O(N+M)이 걸린다.

이제 제거 기록을 거꾸로 따라가며 밝기를 정한다. 처음 정점의 밝기는

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

로 둔다. 지금까지 정한 밝기의 최솟값을 LLL, 최댓값을 RRR이라고 하자.

  • 고립 정점을 추가한다면 밝기를 N−RN-RN−R로 정한다. 기존 모든 밝기와의 합이 NNN 이하이므로 새 간선이 생기지 않는다.
  • 연결 정점을 추가한다면 밝기를 N−L+1N-L+1N−L+1로 정한다. 기존 모든 밝기와의 합이 NNN보다 크므로 모든 기존 정점과 연결된다.

마지막으로 모든 밝기가 111 이상 NNN 이하임을 보이자. 매 단계에서

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

가 유지된다. 또한 정점을 하나 추가할 때마다 R−LR-LR−L은 최대 111 증가하므로, 전체 과정에서 R−L≤N−1R-L\leq N-1R−L≤N−1이다. 두 성질을 합치면 L≥1L\geq1, 을 얻는다.

시간 복잡도는 O(N+M)O(N+M)O(N+M)이고 공간 복잡도도 O(N+M)O(N+M)O(N+M)이다.

Solution written by GPT6

​
=
C+
S−
1
S−1S-1S−1
L≥1
R≤NR\leq NR≤N