QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#193884#7513. Palindromic Beadsucup-team135#WA 2ms4356kbC++204.6kb2023-09-30 17:59:572023-09-30 17:59:59

Judging History

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

  • [2024-03-27 16:34:54]
  • hack成功,自动添加数据
  • (/hack/584)
  • [2024-03-27 16:18:45]
  • hack成功,自动添加数据
  • (/hack/583)
  • [2023-09-30 17:59:59]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4356kb
  • [2023-09-30 17:59:57]
  • 提交

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 &a, int b) {
        if (a >= b) return;
        updates.back().push_back({a, a});
        a = 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) 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;
    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;
    int alld = 0;
    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;
        alld=1;
        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;
        }
    }
    if (!alld) {
        cout << 1 << endl;
        return 0;
    }
    //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 && lca[cur] != h[cur])
            anscolor[c[cur]] = max({3LL, anscolor[c[cur]], 2 + ansdepth.get(depth[lca[cur]])});
        }
        if (v[cur] != -1) {
                ansdepth.update(0, depth[v[cur]], anscolor[c[cur]]);
        //cout << "vup: " << 0 << ' ' << depth[v[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]], 3 + 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: 3644kb

input:

4
1 1 2 2
1 2
2 3
2 4

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3508kb

input:

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

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

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

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

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

output:

1

result:

ok single line: '1'

Test #5:

score: -100
Wrong Answer
time: 2ms
memory: 4356kb

input:

2000
845 1171 345 282 1181 625 754 289 681 493 423 840 1494 318 266 1267 967 379 135 14 39 191 60 972 116 1216 1205 19 194 185 1360 861 379 430 1262 1151 756 65 389 488 277 53 1283 1438 101 1465 195 714 737 980 80 298 961 1326 163 1163 1317 1152 992 35 334 802 1502 486 710 234 555 88 1278 146 46 696...

output:

6

result:

wrong answer 1st lines differ - expected: '5', found: '6'