Recently, I’ve been reorganizing my algorithm templates, which include some data structures and graph algorithms. Since my coding style tends to favor using `std::vector` instead of C-style arrays, I want my templates to be more encapsulated. I admit I’m not very familiar with this style of templates, so I thought of using AI to help me refine them. Below is a template for finding the LCA using Heavy-Light Decomposition:↵
↵
<spoiler summary="LCA (Now)">↵
```cpp↵
struct HLD {↵
/*↵
使用树链剖分求 LCA, HLD tree(edge, 1) -> 初始化↵
tree.lca(u, v) -> 求 u, v 的最近公共祖先↵
*/↵
const std::vector<std::vector<int>> &edge;↵
↵
std::vector<int> fa, dep, son, sz, top;↵
↵
HLD(const std::vector<std::vector<int>> &edge_, int root = 1) : edge(edge_) {↵
int n = (int)edge.size() - 1;↵
fa.assign(n + 1, 0), dep.assign(n + 1, 0), son.assign(n + 1, 0), sz.assign(n + 1, 0), top.assign(n + 1, 0);↵
↵
dfs1(root, 0);↵
dfs2(root, root);↵
}↵
↵
int lca(int u, int v) const {↵
while (top[u] != top[v]) {↵
if (dep[top[u]] < dep[top[v]]) {↵
std::swap(u, v);↵
}↵
u = fa[top[u]];↵
}↵
return dep[u] < dep[v] ? u : v;↵
}↵
↵
private:↵
void dfs1(int u, int f) {↵
fa[u] = f, dep[u] = dep[f] + 1, sz[u] = 1, son[u] = 0;↵
for (auto v : edge[u]) {↵
if (v == f) {↵
continue;↵
}↵
dfs1(v, u);↵
sz[u] += sz[v];↵
if (sz[son[u]] < sz[v]) son[u] = v;↵
}↵
}↵
↵
void dfs2(int u, int t) {↵
top[u] = t;↵
if (son[u] == 0) {↵
return;↵
}↵
dfs2(son[u], t);↵
for (auto v : edge[u]) {↵
if (v == fa[u] || v == son[u]) {↵
continue;↵
}↵
dfs2(v, v);↵
}↵
}↵
};↵
```↵
</spoiler>↵
↵
My previous templates looked like this:↵
↵
<spoiler summary="LCA (Old)">↵
```cpp↵
std::vector<int> e[N];↵
int fa[N], dep[N], son[N], sz[N], top[N];↵
int n, m, s;↵
↵
void dfs1(int u, int father)↵
{↵
fa[u] = father;↵
dep[u] = dep[father] + 1;↵
sz[u] = 1;↵
for (auto to : e[u])↵
{↵
if (to == father)↵
continue;↵
dfs1(to, u);↵
sz[u] += sz[to];↵
if (sz[son[u]] < sz[to])↵
son[u] = to;↵
}↵
}↵
↵
void dfs2(int u, int t)↵
{↵
top[u] = t;↵
if (son[u] == 0)↵
return;↵
dfs2(son[u], t);↵
for (auto to : e[u])↵
{↵
if (to == fa[u] || to == son[u])↵
continue;↵
dfs2(to, to);↵
}↵
}↵
↵
int LCA(int u, int v)↵
{↵
while (top[u] != top[v])↵
{↵
if (dep[top[u]] < dep[top[v]])↵
std::swap(u, v);↵
u = fa[top[u]];↵
}↵
return dep[u] < dep[v] ? u : v;↵
}↵
```↵
</spoiler>↵
↵
Meanwhile, I also directly generated the following template using ChatGPT-5:↵
↵
<spoiler summary="LCA (by ChatGPT)">↵
```cpp↵
#pragma once↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
/*↵
Heavy-Light Decomposition (HLD) for LCA (and a few utilities)↵
-------------------------------------------------------------↵
Usage:↵
HLD hld(n);↵
for (...) hld.addEdge(u, v);↵
hld.build(root); // default root = 1↵
↵
int w = hld.lca(u, v);↵
int d = hld.dist(u, v);↵
bool anc = hld.isAncestor(u, v); // u is ancestor of v ?↵
↵
Notes:↵
- 1-indexed.↵
- Recursion depth is O(n) in worst-case chains. If your judge is strict,↵
compile with bigger stack or convert dfs to iterative.↵
*/↵
↵
struct HLD {↵
int n, root;↵
vector<vector<int>> g;↵
↵
// per-node data↵
vector<int> parent; // parent[u]↵
vector<int> depth; // depth from root↵
vector<int> heavy; // heavy child of u (or -1)↵
vector<int> sz; // subtree size↵
vector<int> head; // head (top) of the heavy path that u is on↵
vector<int> in; // dfs order in[u]↵
vector<int> out; // dfs order out[u] (exclusive)↵
vector<int> rin; // inverse of in[] (node at position)↵
↵
int curTime;↵
↵
explicit HLD(int n_=0) { init(n_); }↵
↵
// Optionally build directly from an adjacency list↵
HLD(const vector<vector<int>>& adj, int root_=1) {↵
init((int)adj.size() - 1);↵
g = adj;↵
build(root_);↵
}↵
↵
void init(int n_) {↵
n = n_;↵
root = 1;↵
g.assign(n + 1, {});↵
parent.assign(n + 1, 0);↵
depth.assign(n + 1, 0);↵
heavy.assign(n + 1, -1);↵
sz.assign(n + 1, 0);↵
head.assign(n + 1, 0);↵
in.assign(n + 1, 0);↵
out.assign(n + 1, 0);↵
rin.assign(n + 1, 0);↵
curTime = 0;↵
}↵
↵
void addEdge(int u, int v) {↵
g[u].push_back(v);↵
g[v].push_back(u);↵
}↵
↵
void build(int root_=1) {↵
root = root_;↵
// 1) sizes, heavy child, parent, depth↵
dfs1(root, 0);↵
// 2) assign head & dfs order↵
dfs2(root, root);↵
}↵
↵
// LCA in O(log N)↵
int lca(int u, int v) const {↵
while (head[u] != head[v]) {↵
if (depth[ head[u] ] < depth[ head[v] ]) swap(u, v);↵
u = parent[ head[u] ];↵
}↵
return depth[u] < depth[v] ? u : v;↵
}↵
↵
// Distance by depths + LCA↵
int dist(int u, int v) const {↵
int w = lca(u, v);↵
return depth[u] + depth[v] - 2 * depth[w];↵
}↵
↵
// Is u ancestor of v?↵
bool isAncestor(int u, int v) const {↵
return in[u] <= in[v] && out[v] <= out[u];↵
}↵
↵
// (Optional) Jump k steps up from u. Requires binary lifting for O(logN).↵
// Here is an O(logN * #chains) version using heads only; good enough for many uses:↵
int jumpUp(int u, int k) const {↵
// Move up whole heavy paths first.↵
while (u && k > 0) {↵
int h = head[u];↵
int up = depth[u] - depth[h];↵
if (k <= up) {↵
// within the same heavy path: just move by index↵
return rin[ in[u] - k ];↵
}↵
// jump to the parent of head and decrease k by the path height + 1 (for head itself)↵
k -= (up + 1);↵
u = parent[h];↵
}↵
return u == 0 ? -1 : u; // if k too large, return -1↵
}↵
↵
private:↵
// First DFS: compute subtree sizes and heavy child↵
void dfs1(int u, int p) {↵
parent[u] = p;↵
depth[u] = (p ? depth[p] + 1 : 0);↵
sz[u] = 1;↵
int maxSub = 0;↵
↵
for (int v : g[u]) if (v != p) {↵
dfs1(v, u);↵
sz[u] += sz[v];↵
if (sz[v] > maxSub) {↵
maxSub = sz[v];↵
heavy[u] = v;↵
}↵
}↵
}↵
↵
// Second DFS: decompose into heavy paths, assign head and in-order indices↵
void dfs2(int u, int h) {↵
head[u] = h;↵
in[u] = ++curTime;↵
rin[curTime] = u;↵
↵
if (heavy[u] != -1) {↵
dfs2(heavy[u], h); // continue the heavy path↵
}↵
for (int v : g[u]) if (v != parent[u] && v != heavy[u]) {↵
dfs2(v, v); // start a new heavy path at v↵
}↵
out[u] = curTime + 1;↵
}↵
};↵
↵
/* ------------------------------↵
Example:↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int n; cin >> n;↵
HLD hld(n);↵
for (int i = 1; i <= n - 1; ++i) {↵
int u, v; cin >> u >> v;↵
hld.addEdge(u, v);↵
}↵
int root = 1;↵
hld.build(root);↵
↵
int q; cin >> q;↵
while (q--) {↵
int u, v; cin >> u >> v;↵
cout << hld.lca(u, v) << "\n";↵
}↵
}↵
*/↵
```↵
</spoiler>↵
↵
As we can see, this template doesn’t really have any issues. In fact, in terms of readability, it is already better than most beginners’ code — or at least easier to maintain.↵
↵
The above examples illustrate that AI has indeed proven to be very effective in maintaining algorithm templates (perhaps partly because such templates already appear in its training data). Whether it is using AI to polish existing templates, assist in modifying them, or directly generate a new one, AI shows strong usability.↵
↵
Of course, in theory, using AI-generated code during contests is clearly not allowed. But my real question lies in the boundary of using such “templates generated by AI in advance.” On one hand, they are indeed produced by AI; on the other hand, they are prepared before the contest, just like how most participants maintain their own template libraries to bring into competitions.↵
↵
As a beginner, I would also like to emphasize that AI has lowered the barrier to learning. With AI tools, we can more easily obtain high-quality reference code, and even detect and correct subtle mistakes we might otherwise overlook. At the very least, outside of contests, they can serve as effective learning tools.↵
↵
Therefore, I started this discussion to hear opinions from the Codeforces community:↵
↵
**Should we allow the use of AI-generated templates?**↵
↵
- Absolutely not [likes:1, o0]↵
- Allow polishing or debugging templates with AI [likes:1, o1]↵
- Allow directly using AI-generated templates [likes:1, o2]↵
↵
**If AI templates are allowed, in which scenarios should they be acceptable?**↵
↵
- Only in pre-contest preparation (AI-assisted template maintenance) [likes:2, o0]↵
- Also during contests (AI-generated or AI-debugged templates) [likes:2, o1]↵
↵
**Should templates indicate when they are generated or refined by AI?**↵
↵
- No, treat them the same as normal templates [likes:3, o0]↵
- Yes, explicitly state AI assistance in the template [likes:3, o1]↵
↵
For options not covered above, share it in the comments.↵
↵
**UPD: I can't understand why this blog was downvoted.**
↵
<spoiler summary="LCA (Now)">↵
```cpp↵
struct HLD {↵
/*↵
使用树链剖分求 LCA, HLD tree(edge, 1) -> 初始化↵
tree.lca(u, v) -> 求 u, v 的最近公共祖先↵
*/↵
const std::vector<std::vector<int>> &edge;↵
↵
std::vector<int> fa, dep, son, sz, top;↵
↵
HLD(const std::vector<std::vector<int>> &edge_, int root = 1) : edge(edge_) {↵
int n = (int)edge.size() - 1;↵
fa.assign(n + 1, 0), dep.assign(n + 1, 0), son.assign(n + 1, 0), sz.assign(n + 1, 0), top.assign(n + 1, 0);↵
↵
dfs1(root, 0);↵
dfs2(root, root);↵
}↵
↵
int lca(int u, int v) const {↵
while (top[u] != top[v]) {↵
if (dep[top[u]] < dep[top[v]]) {↵
std::swap(u, v);↵
}↵
u = fa[top[u]];↵
}↵
return dep[u] < dep[v] ? u : v;↵
}↵
↵
private:↵
void dfs1(int u, int f) {↵
fa[u] = f, dep[u] = dep[f] + 1, sz[u] = 1, son[u] = 0;↵
for (auto v : edge[u]) {↵
if (v == f) {↵
continue;↵
}↵
dfs1(v, u);↵
sz[u] += sz[v];↵
if (sz[son[u]] < sz[v]) son[u] = v;↵
}↵
}↵
↵
void dfs2(int u, int t) {↵
top[u] = t;↵
if (son[u] == 0) {↵
return;↵
}↵
dfs2(son[u], t);↵
for (auto v : edge[u]) {↵
if (v == fa[u] || v == son[u]) {↵
continue;↵
}↵
dfs2(v, v);↵
}↵
}↵
};↵
```↵
</spoiler>↵
↵
My previous templates looked like this:↵
↵
<spoiler summary="LCA (Old)">↵
```cpp↵
std::vector<int> e[N];↵
int fa[N], dep[N], son[N], sz[N], top[N];↵
int n, m, s;↵
↵
void dfs1(int u, int father)↵
{↵
fa[u] = father;↵
dep[u] = dep[father] + 1;↵
sz[u] = 1;↵
for (auto to : e[u])↵
{↵
if (to == father)↵
continue;↵
dfs1(to, u);↵
sz[u] += sz[to];↵
if (sz[son[u]] < sz[to])↵
son[u] = to;↵
}↵
}↵
↵
void dfs2(int u, int t)↵
{↵
top[u] = t;↵
if (son[u] == 0)↵
return;↵
dfs2(son[u], t);↵
for (auto to : e[u])↵
{↵
if (to == fa[u] || to == son[u])↵
continue;↵
dfs2(to, to);↵
}↵
}↵
↵
int LCA(int u, int v)↵
{↵
while (top[u] != top[v])↵
{↵
if (dep[top[u]] < dep[top[v]])↵
std::swap(u, v);↵
u = fa[top[u]];↵
}↵
return dep[u] < dep[v] ? u : v;↵
}↵
```↵
</spoiler>↵
↵
Meanwhile, I also directly generated the following template using ChatGPT-5:↵
↵
<spoiler summary="LCA (by ChatGPT)">↵
```cpp↵
#pragma once↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
/*↵
Heavy-Light Decomposition (HLD) for LCA (and a few utilities)↵
-------------------------------------------------------------↵
Usage:↵
HLD hld(n);↵
for (...) hld.addEdge(u, v);↵
hld.build(root); // default root = 1↵
↵
int w = hld.lca(u, v);↵
int d = hld.dist(u, v);↵
bool anc = hld.isAncestor(u, v); // u is ancestor of v ?↵
↵
Notes:↵
- 1-indexed.↵
- Recursion depth is O(n) in worst-case chains. If your judge is strict,↵
compile with bigger stack or convert dfs to iterative.↵
*/↵
↵
struct HLD {↵
int n, root;↵
vector<vector<int>> g;↵
↵
// per-node data↵
vector<int> parent; // parent[u]↵
vector<int> depth; // depth from root↵
vector<int> heavy; // heavy child of u (or -1)↵
vector<int> sz; // subtree size↵
vector<int> head; // head (top) of the heavy path that u is on↵
vector<int> in; // dfs order in[u]↵
vector<int> out; // dfs order out[u] (exclusive)↵
vector<int> rin; // inverse of in[] (node at position)↵
↵
int curTime;↵
↵
explicit HLD(int n_=0) { init(n_); }↵
↵
// Optionally build directly from an adjacency list↵
HLD(const vector<vector<int>>& adj, int root_=1) {↵
init((int)adj.size() - 1);↵
g = adj;↵
build(root_);↵
}↵
↵
void init(int n_) {↵
n = n_;↵
root = 1;↵
g.assign(n + 1, {});↵
parent.assign(n + 1, 0);↵
depth.assign(n + 1, 0);↵
heavy.assign(n + 1, -1);↵
sz.assign(n + 1, 0);↵
head.assign(n + 1, 0);↵
in.assign(n + 1, 0);↵
out.assign(n + 1, 0);↵
rin.assign(n + 1, 0);↵
curTime = 0;↵
}↵
↵
void addEdge(int u, int v) {↵
g[u].push_back(v);↵
g[v].push_back(u);↵
}↵
↵
void build(int root_=1) {↵
root = root_;↵
// 1) sizes, heavy child, parent, depth↵
dfs1(root, 0);↵
// 2) assign head & dfs order↵
dfs2(root, root);↵
}↵
↵
// LCA in O(log N)↵
int lca(int u, int v) const {↵
while (head[u] != head[v]) {↵
if (depth[ head[u] ] < depth[ head[v] ]) swap(u, v);↵
u = parent[ head[u] ];↵
}↵
return depth[u] < depth[v] ? u : v;↵
}↵
↵
// Distance by depths + LCA↵
int dist(int u, int v) const {↵
int w = lca(u, v);↵
return depth[u] + depth[v] - 2 * depth[w];↵
}↵
↵
// Is u ancestor of v?↵
bool isAncestor(int u, int v) const {↵
return in[u] <= in[v] && out[v] <= out[u];↵
}↵
↵
// (Optional) Jump k steps up from u. Requires binary lifting for O(logN).↵
// Here is an O(logN * #chains) version using heads only; good enough for many uses:↵
int jumpUp(int u, int k) const {↵
// Move up whole heavy paths first.↵
while (u && k > 0) {↵
int h = head[u];↵
int up = depth[u] - depth[h];↵
if (k <= up) {↵
// within the same heavy path: just move by index↵
return rin[ in[u] - k ];↵
}↵
// jump to the parent of head and decrease k by the path height + 1 (for head itself)↵
k -= (up + 1);↵
u = parent[h];↵
}↵
return u == 0 ? -1 : u; // if k too large, return -1↵
}↵
↵
private:↵
// First DFS: compute subtree sizes and heavy child↵
void dfs1(int u, int p) {↵
parent[u] = p;↵
depth[u] = (p ? depth[p] + 1 : 0);↵
sz[u] = 1;↵
int maxSub = 0;↵
↵
for (int v : g[u]) if (v != p) {↵
dfs1(v, u);↵
sz[u] += sz[v];↵
if (sz[v] > maxSub) {↵
maxSub = sz[v];↵
heavy[u] = v;↵
}↵
}↵
}↵
↵
// Second DFS: decompose into heavy paths, assign head and in-order indices↵
void dfs2(int u, int h) {↵
head[u] = h;↵
in[u] = ++curTime;↵
rin[curTime] = u;↵
↵
if (heavy[u] != -1) {↵
dfs2(heavy[u], h); // continue the heavy path↵
}↵
for (int v : g[u]) if (v != parent[u] && v != heavy[u]) {↵
dfs2(v, v); // start a new heavy path at v↵
}↵
out[u] = curTime + 1;↵
}↵
};↵
↵
/* ------------------------------↵
Example:↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int n; cin >> n;↵
HLD hld(n);↵
for (int i = 1; i <= n - 1; ++i) {↵
int u, v; cin >> u >> v;↵
hld.addEdge(u, v);↵
}↵
int root = 1;↵
hld.build(root);↵
↵
int q; cin >> q;↵
while (q--) {↵
int u, v; cin >> u >> v;↵
cout << hld.lca(u, v) << "\n";↵
}↵
}↵
*/↵
```↵
</spoiler>↵
↵
As we can see, this template doesn’t really have any issues. In fact, in terms of readability, it is already better than most beginners’ code — or at least easier to maintain.↵
↵
The above examples illustrate that AI has indeed proven to be very effective in maintaining algorithm templates (perhaps partly because such templates already appear in its training data). Whether it is using AI to polish existing templates, assist in modifying them, or directly generate a new one, AI shows strong usability.↵
↵
Of course, in theory, using AI-generated code during contests is clearly not allowed. But my real question lies in the boundary of using such “templates generated by AI in advance.” On one hand, they are indeed produced by AI; on the other hand, they are prepared before the contest, just like how most participants maintain their own template libraries to bring into competitions.↵
↵
As a beginner, I would also like to emphasize that AI has lowered the barrier to learning. With AI tools, we can more easily obtain high-quality reference code, and even detect and correct subtle mistakes we might otherwise overlook. At the very least, outside of contests, they can serve as effective learning tools.↵
↵
Therefore, I started this discussion to hear opinions from the Codeforces community:↵
↵
**Should we allow the use of AI-generated templates?**↵
↵
- Absolutely not [likes:1, o0]↵
- Allow polishing or debugging templates with AI [likes:1, o1]↵
- Allow directly using AI-generated templates [likes:1, o2]↵
↵
**If AI templates are allowed, in which scenarios should they be acceptable?**↵
↵
- Only in pre-contest preparation (AI-assisted template maintenance) [likes:2, o0]↵
- Also during contests (AI-generated or AI-debugged templates) [likes:2, o1]↵
↵
**Should templates indicate when they are generated or refined by AI?**↵
↵
- No, treat them the same as normal templates [likes:3, o0]↵
- Yes, explicitly state AI assistance in the template [likes:3, o1]↵
↵
For options not covered above, share it in the comments.↵
↵
**UPD: I can't understand why this blog was downvoted.**
