QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#238685 | #7513. Palindromic Beads | zzy0922 | WA | 0ms | 11004kb | C++14 | 4.8kb | 2023-11-04 17:16:14 | 2023-11-04 17:16:14 |
Judging History
answer
#include <bits/stdc++.h>
inline void chkmax(int &x, const int &v) {
x = std::max(x, v);
}
const int N = 200005;
int n;
int c[N];
std::vector<int> t[N];
int pre[N];
namespace Seg_Seg {
struct node {
int ls, rs, val;
}tree[40000005];
#define ls(p) tree[p].ls
#define rs(p) tree[p].rs
#define val(p) tree[p].val
int rt[N << 2], tot;
void build(int p, int l, int r) {
rt[p] = ++tot;
if (l == r) return;
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
}
inline void pushup(int p) {
val(p) = 0;
if (ls(p)) chkmax(val(p), val(ls(p)));
if (rs(p)) chkmax(val(p), val(rs(p)));
}
void _ins(int p, int l, int r, int x, int v) {
if (l == x && r == x) {
val(p) = std::max(val(p), v);
return;
}
int mid = (l + r) >> 1;
if (x <= mid) {
if (!ls(p)) ls(p) = ++tot;
_ins(ls(p), l, mid, x, v);
}
else {
if (!rs(p)) rs(p) = ++tot;
_ins(rs(p), mid + 1, r, x, v);
}
pushup(p);
}
int _qry(int p, int l, int r, int ll, int rr) {
if (!p) return 0;
if (ll > r || rr < l) return 0;
if (ll <= l && r <= rr) return val(p);
int mid = (l + r) >> 1;
return std::max(_qry(ls(p), l, mid, ll, rr), _qry(rs(p), mid + 1, r, ll, rr));
}
void ins(int p, int l, int r, int x, int y, int v) {
if (x > r || x < l) return;
// std::cout << rt[p] << '\n';
_ins(rt[p], 1, n, y, v);
if (x == l && x == r) return;
int mid = (l + r) >> 1;
ins(p << 1, l, mid, x, y, v);
ins(p << 1 | 1, mid + 1, r, x, y, v);
}
int qry(int p, int l, int r, int l1, int r1, int l2, int r2) {
if (l1 > r || r1 < l) return 0;
if (l1 <= l && r <= r1) return _qry(rt[p], 1, n, l2, r2);
int mid = (l + r) >> 1;
return std::max(qry(p << 1, l, mid, l1, r1, l2, r2), qry(p << 1 | 1, mid + 1, r, l1, r1, l2, r2));
}
}
using Seg_Seg::ins;
using Seg_Seg::qry;
int dep[N], fa[N], top[N], siz[N], son[N], dfn[N], out[N], tot;
void dfs1(int u) {
siz[u] = 1;
for (const int &v : t[u]) {
if (v == fa[u]) continue;
fa[v] = u;
dep[v] = dep[u] + 1;
dfs1(v);
siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
out[u] = tot;
}
void dfs2(int u, int tp) {
dfn[u] = ++tot;
top[u] = tp;
if (son[u]) dfs2(son[u], tp);
for (const int &v : t[u]) {
if (v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
out[u] = tot;
}
inline int lca(int x, int y) {
int fx = top[x], fy = top[y];
while (fx != fy) {
if (dep[fx] > dep[fy]) x = fa[fx], fx = top[x];
else y = fa[fy], fy = top[y];
}
return dep[x] < dep[y] ? x : y;
}
inline int dis(const int &u, const int &v) {
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
std::vector<std::pair<int, int> > pr;
int main() {
std::cin >> n;
Seg_Seg::build(1, 1, n);
// ins(1, 1, n, 1, 5, 2);
// std::cout << "qry: " << qry(1, 1, n, 1, 2, 1, 5) << '\n';
for (int i = 1; i <= n; i++) std::cin >> c[i];
for (int i = 1, u, v; i <= n - 1; i++) {
std::cin >> u >> v;
t[u].push_back(v);
t[v].push_back(u);
}
dfs1(1);
dfs2(1, 1);
// for (int i = 1; i <= n; i++) std::cout << top[i] << '\n';
// return 0;
for (int i = 1; i <= n; i++) {
if (pre[c[i]]) {
int u = pre[c[i]], v = i;
pr.emplace_back(u, v);
// std::cout << u << ' ' << v << ' ' << dis(u, v) << '\n';
}
pre[c[i]] = i;
}
std::sort(pr.begin(), pr.end(), [&](std::pair<int, int> a, std::pair<int, int> b) {
return dis(a.first, a.second) > dis(b.first, b.second);
});
int max = 1;
for (const auto &p : pr) {
int u = p.first, v = p.second;
if (dfn[u] > dfn[v])
std::swap(u, v);
int res = 2;
if (dfn[u] < dfn[v] && out[u] >= out[v]) {
res = std::max(qry(1, 1, n, 1, dfn[u], dfn[v], out[v]), qry(1, 1, n, out[u], n, dfn[v], out[v])) + 2;
// std::cout << "qry : " << 1 << ' ' << dfn[u] - 1 << ' ' << dfn[v] + 1 << ' ' << out[v] << '\n';
// std::cout << "qry : " << out[u] + 1 << ' ' << n << ' ' << dfn[v] + 1 << ' ' << out[v] << '\n';
} else {
res = qry(1, 1, n, dfn[u], out[u], dfn[v], out[v]) + 2;
// std::cout << "qry : " << dfn[u] + 1 << ' ' << out[u] << ' ' << dfn[v] + 1 << ' ' << n << '\n';
}
ins(1, 1, n, dfn[u], dfn[v], res);
ins(1, 1, n, dfn[v], dfn[u], res);
// std::cout << "ins : " << dfn[u] << ' ' << dfn[v] << '\n';
chkmax(max, res + (dis(u, v) != 1));
}
std::cout << max << '\n';
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 11004kb
input:
4 1 1 2 2 1 2 2 3 2 4
output:
4
result:
wrong answer 1st lines differ - expected: '3', found: '4'