QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#196426#7513. Palindromic Beadsucup-team135WA 0ms3640kbC++204.5kb2023-10-01 17:17:482023-10-01 17:17:49

Judging History

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

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

answer

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
struct MaxTree {
    int n;
    vector<int> mx;
    MaxTree(int n) : n(n), mx(2 * n) {}
    vector<vector<pair<int, int>>> updates;
    void ckmax(int i, int b) {
        if (mx[i] >= b) return;
        updates.back().push_back({i, mx[i]});
        mx[i] = b;
    }
    void update(int l, int r, int x) {
        updates.emplace_back();
        for (l += n, r += n; l < r; l /= 2, r /= 2) {
            if (l & 1) ckmax(mx[l++], x);
            if (r & 1) ckmax(mx[--r], x);
        }
    }
    int get(int i) {
        int ans = 0;
        for (i += n; i > 0;i /= 2) ans = max(ans, mx[i]);
        return ans;
    }
    void rollback() {
        auto x = updates.back();
        reverse(all(x));
        for (auto [u, v]: x) mx[u] = v;
        updates.pop_back();
    }
};
int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n;
    cin >> n;
    vector<int> c(n);
    for (int &x : c) cin >> x, --x;
    map<int, vector<int>> w;
    vector<vector<int>> g(n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 0; i < n; ++i) w[c[i]].push_back(i);
    vector<int> depth(n), tin(n), tout(n);
    vector<vector<int>> up(__lg(n) + 2, vector<int>(n));
    int time = 0;
    depth[0] = 1;
    auto dfs = [&](auto dfs, int cur, int prev) -> void {
        tin[cur] = time++;
        for (int nxt : g[cur]) {
            if (nxt == prev) continue;
            depth[nxt] = depth[cur] + 1;
            up[0][nxt] = cur;
            dfs(dfs, nxt, cur);
        }
        tout[cur] = time++;
    };
    dfs(dfs, 0, 0);
    for (int lvl = 1; lvl < up.size(); ++lvl) {
        for (int i = 0; i < n; ++i) up[lvl][i] = up[lvl - 1][up[lvl - 1][i]];
    }
    ////cout << "a" << endl;
    auto get_lca = [&](int u, int v) {
        for (int k = __lg(n); k >= 0; --k) if (depth[up[k][u]] >= depth[v]) u = up[k][u];
        for (int k = __lg(n); k >= 0; --k) if (depth[up[k][v]] >= depth[u]) v = up[k][v];
        assert(depth[u] == depth[v]);
        for (int k = __lg(n); k >= 0; --k) if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
        return u == v ? u : up[0][u];
    };
    ////cout << "b" << endl;
    vector<int> v(n, -1), h(n, -1), lca(n, -1);
    for (auto [c, vec] : w) {
        if (vec.size() == 1) continue;
        assert(vec.size() == 2);
        auto [a, b] = make_tuple(vec[0], vec[1]);
        ////cout << a << ' ' << b << endl;
        if (tin[a] > tin[b]) swap(a, b);
        int l = get_lca(a, b);
        lca[a] = lca[b] = l;
        assert(l != b);
        if (l == a) {
            v[b] = a;
        } else {
            h[a] = b;
        }
    }
    //cout << "c" << endl;
    MaxTree ansdepth(n);
    vector<int> anscolor(n);
    auto dfs2 = [&](auto dfs2, int cur, int prev) -> void {
        if (v[cur] != -1) {
            anscolor[c[cur]] = max(2 + ansdepth.get(depth[v[cur]]), 2LL + (depth[cur] - depth[v[cur]] > 1));
        } else if (lca[cur] != cur) {
            if (lca[cur] != -1)
            anscolor[c[cur]] = max({3LL, anscolor[c[cur]], 2 + ansdepth.get(depth[lca[cur]] - 1)});
        }
        if (v[cur] != -1) {
                ansdepth.update(0, depth[v[cur]], anscolor[c[cur]]);
        //cout << "vup: " << 0 << ' ' << depth[cur] << ' ' << anscolor[c[cur]] << endl;
        }
        for (int nxt : g[cur]) {
            if (nxt != prev) dfs2(dfs2, nxt, cur);
        }
        if (v[cur] != -1) ansdepth.rollback();
    };
    dfs2(dfs2, 0, 0);
    MaxTree anstin(2 * n);
    auto dfs3 = [&](auto dfs3, int cur, int prev) -> void {
        if (h[cur] != -1) {
            anscolor[c[cur]] = max(anscolor[c[cur]], 2 + anstin.get(tin[h[cur]]));
        }
        if (h[cur] != -1) {anstin.update(tin[h[cur]], tout[h[cur]], anscolor[c[cur]]);
        //cout << "tup: " << tin[h[cur]] << ' ' <<tout[h[cur]]<<' '<< anscolor[c[cur]];
        }
        for (int nxt : g[cur]) {
            if (nxt != prev) dfs3(dfs3, nxt, cur);
        }
        if (h[cur] != -1) anstin.rollback();
    };
    dfs3(dfs3, 0, 0);
    int ans = *max_element(all(anscolor));
    //cout << "ans:  " << endl;
    cout << max(1LL, ans) << '\n';
    return 0;
}
/*
5
1 2 3 2 1
1 2 2 3 3 5 5 4
5
*/
/*
4
1 1 2 2
1 2
2 3
2 4

5
1 3 2 2 1
1 2
2 3
3 4
4 5
*/

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3640kb

input:

4
1 1 2 2
1 2
2 3
2 4

output:

3

result:

ok single line: '3'

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3572kb

input:

5
1 3 2 2 1
1 2
2 3
3 4
4 5

output:

3

result:

wrong answer 1st lines differ - expected: '4', found: '3'