比赛可以鸽，暂别不行。

我们几个管理员 Qingyu, Qingyu, Qingyu 和我在过去的半年中，组织和举办了不少的比赛，也还算及时地将官方比赛题目上传到了 QOJ 中。

我一直非常喜欢 UOJ，在去年收到 Qingyu 的邀请后，我思考了一段时间，并决定来当 QOJ 管理，我想为这个美好的 OJ 献出自己的一份力量，让这个 OJ 变得更加好，如今看来，当时的目标也基本实现了。

在当管理的一年中，还是有很多事让我记忆深刻的，还记得 XXI Open Cup named after E.V. Pankratiev, Grand Prix of Siberia; XXI Open Cup named after E.V. Pankratiev, Grand Prix of Eurasia; 7 February, 2021 — Waterloo local contest; NOIP 2020; Petrozavodsk Winter 2021. Day 9. Grand Prix of Suwon; XXI Open Cup named after E.V. Pankratiev; Grand Prix of Suwon; Petrozavodsk Winter 2021. Day 8. Belarusian SU Contest; XXI Open Cup named after E.V. Pankratiev; Grand Prix of Belarus; Petrozavodsk Winter 2021. Day 7. North American Contest 1; Petrozavodsk Winter 2021. Day 6. PKU Contest 2; Petrozavodsk Winter 2021. Day 5. Almost Retired Dandelion Contest; XXI Open Cup named after E.V. Pankratiev; Grand Prix of Nizhny Novgorod; Petrozavodsk Winter 2021. Day 4. PKU Contest (Common Contest 1); Petrozavodsk Winter 2021. Day 3. Nordic+ Contest 2020 (NCPC-2020 with some BAPC/UKIEPC 2020); Petrozavodsk Winter 2021. Day 2. UPC Contest; Petrozavodsk Winter 2021. Day 1. Jagiellonian U Contest; XXI Open Cup named after E.V. Pankratiev; Grand Prix of Krakow; Nordic Collegiate Programming Contest 2020; Potyczki Algorytmiczne 2020; Runda 5; Potyczki Algorytmiczne 2020; Runda 4; Potyczki Algorytmiczne 2020; Runda 3; Potyczki Algorytmiczne 2020; Runda 2; Potyczki Algorytmiczne 2020; Runda 1; Potyczki Algorytmiczne 2020; Runda próbna; 2019-2020 ICPC Northwestern Europe Regional Contest; 2018-2019 ICPC Northwestern Europe Regional Contest; USACO 2020 January Contest (Platinum); USACO 2019 December Contest (Platinum); The 2020 Benelux Algorithm Programming Contest; USACO 2019 February Contest (Platinum); USACO 2019 January Contest (Platinum); USACO 2018 December Contest (Platinum); 2017-2018 ICPC Northwestern Europe Regional Contest; Nordic Collegiate Programming Contest 2019; 2019-2020 ICPC Southwestern Europe Regional Contest; 2020 Canadian Computing Olympiad Day 2; 2020 Canadian Computing Olympiad Day 1; International Olympiad in Informatics 2020 Day 2; International Olympiad in Informatics 2020 Day 1; Petrozavodsk Summer 2020. Day 6. Korean Contest; Petrozavodsk Summer 2020. Day 5. JAG Summer 2019+; Petrozavodsk Summer 2020. Day 4. Xi Lin Contest 6; Petrozavodsk Summer 2020. Day 3. Songyang Chen Contest; Petrozavodsk Summer 2020. Day 2. SPb SU LOUD ENOUGH Contest; XXI Open Cup named after E.V. Pankratiev; Grand Prix of SPb; Petrozavodsk Summer 2020. Day 1. Warsaw U Contest; USACO 2018 February Contest (Platinum); USACO 2018 January Contest (Platinum); USACO 2017 December Contest (Platinum); 2020-2021 ICPC North America - Pacific Northwest Regional Contest - Division 2; 2020-2021 ICPC North America - Pacific Northwest Regional Contest - Division 1; 2020-2021 ICPC North America - Mid-Atlantic USA Regional Contest; 2020-2021 ICPC North America - Mid-Central USA Programming Contest; 2020-2021 ICPC North America - East Central NA Regional Contest; 2020-2021 ICPC North America - Rocky Mountain Regional Contest; 2019-2020 ICPC North America - Rocky Mountain Regional Contest; Russia Open 2020 High School Team Programming Contest 2020-09-08 08:30:00 3 hours 30 minutes No ×0 IOI 2018 中国国家队清华集训 Day 4 (CTT 2017 Day 4); IOI 2018 中国国家队清华集训 Day 3 (CTT 2017 Day 3); IOI 2018 中国国家队清华集训 Day 2 (CTT 2017 Day 2); IOI 2018 中国国家队清华集训 Day 1 (CTT 2017 Day 1); 前 D 题发生了一系列事故，导致比赛前一天 Qingyu 哥哥晚上一点多写好 std，我三多造好数据，然后还发现了同样没睡在内卷的 hy，第二天起来一看 Qingyu 说他第一步假了，暴力和 std 都是错的，换上了现在的题意，11 点 Qingyu 写完 std 然后我造数据传好就弃疗了。以及后来的 QOJ Training Series 和 Qingyu 哥哥熬夜造 E 题等等 （主要原因还是我们太鸽），不过相信下一届管理员会比我们做得更好！

现在 NOI 也顺利结束了，又一批 OIer 完成了他们最重要的一战，而 QOJ 也到了换届的环节，下一届将有四个管理员，他们是：

Qingyu、Qingyu、Qingyu、Qingyu

祝你们一切顺利，QOJ 越办越好！

Online Contests

Opentrains

• Opentrains Logins
• Opentrains Contests
• A complete list
• Official contest list

Yandex

• Yandex Contests

Open Cup

• opentrains
• Official Website
• List of all Open Cup contests

AtCoder

• AtCoder test cases
• Kenkoooo

TopCoder

• Contest Archive
• Problem Archive

Polish Contests

• Olimpiada Informatyczna
• Szkopuł
• OIOIOI

Training Camp

• List of all Petrozavodsk Contests

OI Contests

ICPC Contests

http://oj.qingyu.us/archive/icpc/

为了避免自己的账户泄露，建议不要在大机房中使用浏览器的“保存密码”功能！！

若认为自己的密码已经泄露，需要在修改密码后使用 登出所有活跃会话 功能，否则此前认证过的会话可能不会失效。

同时，为了避免权限组的题目泄露，hydd 大神指示各位 hy 的粉丝 使用强度较高的密码，请不要使用诸如 123456、114514、19260817、hyakcts、ilovechino 的弱口令。

FTP 所有账户已重置，请有 FTP 权限的群友查看系统消息获取最新的用户密码。对于 Archive 中一些公开的测试数据，建议大家转至 Google Drive 镜像进行下载。

不建议在博客中写模拟赛题的题解，如果需要写内部题的题解，一定注意添加权限。所有内部题目的讨论博客需要拥有 access-secret-blogs 权限与校内团队（目前有 $12,16,17,19,22$ 五个团队）权限才可以查看。

本公告的最终解释权归 hydd 所有。

Last Updated: December 2025

Judgehost Specification

The judgehosts of QOJ are all hosted on Microsoft Azure. All judgehosts have the identical specifications:

• OS: Ubuntu 24.04.1 LTS
• RAM: 8 GiB
• CPU: Intel(R) Xeon(R) Platinum 8570

Language Details

Unless specified in the problem meta page, you may submit your solution in any of our supported languages. Note that IOI and most other Olympiads support C++ exclusively, so problems with graders typically only support C++. Always check the problem meta information before starting!

• C
• C++
• D
• Fortran
• Go
• Haskell
• Java
• Kotlin
• Lean 4.23.0
• Pascal
• Python 3 (CPython 3.13 or PyPy 3.11)
• Ruby
• Rust

C++ (C++98, C++11, C++14, C++17, C++20, C++23, C++26)

All C++ submissions are compiled using GCC 15.2.0. The detailed compilation tag is as follows:

g++ -o answer -x c++ answer.code -lm -O2 -DONLINE_JUDGE -std=c++XX

The -std=c++XX flag will be set according to your chosen standard (98, 11, 14, 17, 20, or 23).

C (C99, C11)

All C submissions are compiled using GCC 15.2.0. The detailed compilation tag is as follows:

gcc -o answer -x c answer.code -lm -O2 -DONLINE_JUDGE -std=cXX

The -std=cXX flag will be set to either c99 or c11 based on your selection.

Java (Java 8, Java 11, Java 17, Java 21)

Note: As of January 13, 2025, Java 7 and Java 14 are no longer supported by QOJ.

We use Open JDK for all Java submissions.

• Java 8: openjdk version "1.8.0_462"
• Java 11: openjdk 11.0.28
• Java 17: openjdk 17.0.16
• Java 21: openjdk 21.0.8

Flags -Xmx2048m, -Xss1024m, and -XX:ActiveProcessorCount=1 will be added when running Java programs.

Python (CPython 3.13 / PyPy 3.11)

Note: As of Dec 20, 2023, Python 2 is no longer supported by QOJ.

The Python Interpreters we used are CPython 3.13.7 and PyPy 3.11.

Rust

The Rust compiler we used is rustc 1.92.0 (ded5c06cf 2025-12-08). The detailed compilation tag is as follows:

rustc -o answer -C opt-level=3 --edition=2021 answer.code

D

The D compiler we used is DMD64 D Compiler v2.109.1. The detailed compilation tag is as follows:

dmd answer -O -release -inline -boundscheck=off

Pascal

The Pascal compiler we used is fpc, Free Pascal Compiler version 3.2.2. The detailed compilation tag is as follows:

fpc answer.code -O2

Haskell

The Haskell compiler we used is ghc, The Glorious Glasgow Haskell Compilation System, version 9.4.7. The detailed compilation tag is as follows:

ghc -O2 -rtsopts -XSafe -no-keep-hi-files -no-keep-o-files -static -o answer answer.hs

Kotlin

The Kotlin compiler we used is kotlinc-jvm 2.1.0 (JRE 21.0.5+11-Ubuntu-1ubuntu124.04). The JVM option we used to run Kotlin programs is the same as we used in Java programs.

Go

The Go compiler we used is go version go1.22.2 linux/amd64.

go build -o answer -ldflags -s -w -trimpath

Ruby

The Ruby version we used is Ruby 3.4.8.

Fortran 95 / Fortran 2018

The Fortran compiler we used is GNU Fortran 15.0.1. The detailed compilation tag is as follows:

gfortran -o answer answer.f90  -O2 -DONLINE_JUDGE -std=fX

The -std=fX flag will be set according to your chosen standard (95 or 2018).

Discovery Hailiang Logins

这个东西在若干个群友监督下随机生成的,他们都表示直接通过!

随机生成器是 @Qingyu 瞎写的,有问题就喷他.

在随机现场的 @hydd, @Lenstar 表示这个真的是一次随机生成的.

因为一些原因去随便找了个爬虫爬了下来所有比赛名称。

下面是部分内容展示，完整版请见附件下载：

Part I: contest.yandex.ru

最后更新：2021.02.19，更新至比赛 id 25209

……

下载附件

不写了

本帖所有内容均来自 Open Cup News 频道(https://t.me/opencup_ru), 若信息有冲突请以频道内容为准.

本帖所提及的发帖时间均指莫斯科时间 (UTC +3)

• 05/27/2020 18:48: The rules for the next season will be adjusted soon, so stay tuned
• 09/24/2020 13:03: The next season starts with GP of Eurasia at the Sep 27, followed by some GP based on one of Petrozavodsk problemsets in a week and the GP of Korea in two weeks.
• 09/25/2020 14:24: New changes in the OpenCup rules are coming. First, there will be no Div 1 Yandex Sponsor Championship for NERC ICPC teams this year. Second: the team with participant who is author or tester of the some Grand Prix, earns the team's season average score for this Grand Prix (note that this value changes through whole season and will be finalized only at the season ends). Third: there may be some changes in team formation rule, those changes are under consideration
• 10/26/2020 14:24: GP of Siberia will be held at the Nov 1, GP of Weihai at the Nov 8. As for Nov 15, there still no decision if there will be any Grand Prix.
• 11/26/2020 04:08: GP of NorthBeach (aka GP of Bei Sha Tan) will be held at the Nov 29.
• 12/14/2020 11:09: GP of Xiaomi will be held at the Dec 20. For the teams participated in the MW results from MW will be integrated.. Usual time. The early participation hopefully will be opened very soon.
• 12/24/2020 02:04: GP of Samara will be held at the Jan 3. 2021. For the teams participated in the MW results from MW will be integrated. Usual time. The early participation will be opened
• 12/24/2020 02:11: No GP is planned for Dec 27 due to intersection with AtCoder event
• 01/09/2021 18:24: GP of Nanjing will be held on Jan 10 (tomorrow)
• 01/28/2021 23:48: GP of Krakow will be held on Jan 31, usual time. For the Petrozavodsk camp teams the camp participation will count
• 01/28/2021 23:49: Feb 7 and Feb 14 here will be GP too, based on Petrozavodsk contests. Names of the GP will be announced later
• 01/29/2021 10:30: GP of Nizhny Novgorod will be held on Feb 7, usual time. For the Petrozavodsk camp teams and ICPC/Shanghai Training camp teams the camp participation will count.
• 02/06/2021 17:03: GP of Belarus will be held on Feb 14, usual time. For the Petrozavodsk camp teams the camp participation will count
• 02/06/2021 17:04: GP of Suwon will be held on Feb 21, usual time. For the Petrozavodsk camp teams the camp participation will count
• 02/25/2021 04:12: GP of Tokyo will be held on Feb 28, usual time.
• 04/23/2021 23:18: GP of China will be held on May 2, usual time. For the MW teams the camp participation will count
• 05/03/2021 21:43: GP of Urals will be held on May 9, usual time. Ural championship onsite teams results will be counted
• 05/03/2021 21:44: With good chances there will be two GP at May 16 and May 23, names and other details will be told at short time
• 05/06/2021 14:11: The GP at May 16 is cancelled. GP of Southern Europe will be held on May 23, usual time.
• 05/16/2021 21:15: Due to SEERC is moved from Sat to Sun, the GP of Southern Europe will start at 16:00 Moscow time (5 hours later than the standard time). The ext teams link appears approximatelly at the standard time or hour later.
• 05/16/2021 21:16: Today the final contest for the XX Open Cup was held online. The winner is USA1, the runner-up is Past Glory, third place goes to Polish Mafia. Congratultations to the winners!
• 05/23/2021 11:06: The ext teams may start the GP of Southeastern Europe from now. The link for the GP of Southeastern Europe is http://official.contest.yandex.com/opencupXXI/contest/27619/enter
• 06/02/2021 17:21: GP of Beijing will be held on June 6, usual time, on the CCPC Finals tasks

本帖最后更新于 06/03/2021 09:58 (UTC +3)

A

把所有形如$(a,ka)$的路径提出来，共有$O(n\log n)$条路径，后面将这种路径称为限制。

考虑答案路径如果要不合法，那么必然覆盖了至少一条完整的限制。

考虑覆盖限制$(u,v)$的路径$(a,b)$，设$dfn_x$表示$x$的$dfs$序，$end_x$表示$x$的子树中最大的$dfs$序，不妨设$dfn_u < dfn_v,dfn_a < dfn_b$。

1. 当$u$是$v$的祖先的时候，考虑$g$是离$u$最近的路径$(u,v)$上的点，要么$dfn_a < dfn_g,dfn_v\leq dfn_b\leq end_v$，要么$dfn_v\leq dfn_a\leq end_v,dfn_b>end_g$。
2. 当$u$不是$v$的祖先的时候，显然$dfn_u\leq dfn_a\leq end_u, dfn_v\leq dfn_b\leq end_v$。

第一种情况构成了$2$个矩形，第二种情况构成了$1$个矩形。

最终我们只要求出所有矩形的并然后取个反即可，扫描线$+$线段树，总复杂度$O(n\log^2 n)$。

B

观察一下可以发现，如果将同一行与同一列的$1$用边连起来，一种方案可以拆成很多个环，从这个方面入手。

设$f_n$表示$n\times n$矩阵的答案，我们枚举第一行所在环的大小，那么有递推式： $$f_n = \sum_{i = 2}^{n}A_i\cdot \binom{n}{i}\cdot \binom{n - 1}{i - 1}\cdot f_{n - i}$$

其中$A_i$表示$i\times i$的矩阵只有一个环的方案数，$\binom{n}{i}$表示选出$i$列，$\binom{n-1}{i-1}$表示选出除了第$1$行的剩下的$i-1$行。

先给出结论：$A_n = \frac{n!(n-1)!}{2}$，那么式子化成： $$f_n = \sum_{i = 2}^{n}\frac{i!(i-1)!}{2}\cdot \binom{n}{i}\cdot \binom{n - 1}{i - 1}\cdot f_{n - i}$$

将组合数拆开化简，得到： $$f_n = \frac{n!(n-1)!}{2}\sum_{i = 2}^{n}\frac{f_{n-i}}{((n-i)!)^2}$$

设$g_n = \frac{f_n}{(n!)^2}$，那么有： $$g_n = \frac{1}{2n}\sum_{i = 2}^{n}g_{n - i}$$

维护前缀和即可，复杂度$O(n)$。

现在考虑怎么证明$A_n = \frac{n!(n-1)!}{2}$。

先$n!$每行每列放一个$1$，设$p_i$表示第$i$行$1$的列编号。在$p_1$列放第二个$1$ 有$n-1$种方案，假设第二个$1$行号为$q_i$，那么接下来考虑$p_{q_i}$列，这列第二个$1$有$n-2$ 种放法，因为不能在此时返回第一行，再加上已有$2$个$1$的行不能再放$1$。接下来就是$n-3...$。除以二是因为这个过程的逆过程也被计算过了。

C

一眼费用流裸题，但是数据范围有点大，考虑动态维护流量。

设当前加入的点编号为$x$，因为深度是$O(\log n)$的，因此我们可以枚举$x$和$x$要到的点的LCA，对于当前LCA设为$g$，我们需要求出$g$往子树中走最小的代价使得可以流到一个还有剩余容量的点，设为$down_g$。注意子树中行走的代价可以根据每条边的流量正负来确定，因此要维护每条边的流量，其实就是手动维护网路流。我们需要求出$down_g+cost(x\rightarrow g)$中代价最小的那个，然后暴力维护每条边的流量即可。

复杂度$O(n\log n)$。

似乎 BZOJ 挂了以后就没有地方有 JSOI 2017 的题目了，于是上传了一下。

• JSOI 2017 Round 1 Day 1: https://qoj.ac/contest/121
  • [JSOI 2017] 王国
  • [JSOI 2017] 预言
  • [JSOI 2017] 代码
• JSOI 2017 Round 1 Day 2: https://qoj.ac/contest/122
  • [JSOI 2017] 骑士
  • [JSOI 2017] 街道
  • [JSOI 2017] 奥术
• JSOI 2017 Round 2 Day 1: https://qoj.ac/contest/123
  • [JSOI 2017] 原力
  • [JSOI 2017] 隧道
  • [JSOI 2017] 税收
• JSOI 2017 Round 2 Day 2: https://qoj.ac/contest/124
  • [JSOI 2017] 码农
  • [JSOI 2017] 博弈
  • [JSOI 2017] 魔法

Enjoy!