2023-11-10

省流：Floyd 写成 ijk

案发地点

CF475B Strongly Connected City

挂分代码

for (int i = 1; i <= tot; i++)
    for (int j = 1; j <= tot; j++)
        for (int k = 1; k <= tot; k++)
            f[i][j] |= f[i][k] & f[k][j];

挂分后果

duel 因耽误时间失败。

#2854: _YXJS_ 负 Error_Yuan
on 475B(*1400)
From 2023-11-10 15:05:53 to 2023-11-10 15:12:27, lasted for 0:06:34

挂分原因

Floyd 枚举顺序应该为先枚举中间转移点即 $k,i,j$。

正确代码

for (int k = 1; k <= tot; k++)
    for (int i = 1; i <= tot; i++)
        for (int j = 1; j <= tot; j++)
            f[i][j] |= f[i][k] & f[k][j];

2023-11-11

省流：DSU 路径压缩写错

案发地点

ABC328F Good Set Query

挂分代码

int F(int u) { return fa[u] ^ u ? son[fa[u] = F(fa[u])].push_back(u), fa[u] : u; }

挂分后果

6 发罚时，perf 2k+ -> perf 1k5，甚至掉了 5 分。

挂分原因

并查集路径压缩一定是在同一棵子树内进行的，不需要反复 push 自己到祖先上。

正确代码

int F(int u) { return fa[u] ^ u ? fa[u] = F(fa[u]) : u; }

2023-11-19

省流：根号分治既有 $b$ 又有 $B$

案发地点

ABC329F Colored Ball

挂分代码

else if (sz[a] >= B && sz[B] < B) // 大小

挂分后果

满屏黄色的 WA，哈哈。

挂分原因

$B$ 是根号分治的阈值，$b$ 是读入，大小写打反了。

正确代码

else if (sz[a] >= B && sz[b] < B) // 大小