QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#238685#7513. Palindromic Beadszzy0922WA 0ms11004kbC++144.8kb2023-11-04 17:16:142023-11-04 17:16:14

Judging History

你现在查看的是最新测评结果

  • [2024-03-27 16:34:54]
  • hack成功,自动添加数据
  • (/hack/584)
  • [2024-03-27 16:18:45]
  • hack成功,自动添加数据
  • (/hack/583)
  • [2023-11-04 17:16:14]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:11004kb
  • [2023-11-04 17:16:14]
  • 提交

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'