oj.uz

Submission #546615

# Submission time Handle Problem Language Result Execution time Memory
546615 2022-04-07T21:24:05 Z Olympia Lampice (COCI19_lampice) C++17
42 / 110
 5000 ms 14228 KB 
#include <cmath>
#include <iostream>
#include <set>
#include <climits>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <string>
#include <vector>
#include <iomanip>
#include <unordered_map>
#include <type_traits>
#include <string>
#include <queue>
#include <map>

using namespace std;

const int MOD = 1e9 + 9;
const int BASE = 293;
const int inv = 706484648;


class Tree {
public:
    vector<int> sub, depth, parent;
    vector<int64_t> dp1, dp2;
    vector<bool> hasVisited;
    vector<int> adj[(int)5e4];
    vector<int64_t> powr, ipowr;
    int dp[(int)5e4][17];
    string s;
    int sz;
    int dfs1 (int curNode, int prevNode) {
        sub[curNode] = 1;
        for (int i: adj[curNode]) if (!hasVisited[i] && i != prevNode) sub[curNode] += dfs1(i, curNode);
        return (sz = sub[curNode]);
    }
    int get_centroid (int curNode, int prevNode) {
        for (int i: adj[curNode]) if (!hasVisited[i] && i != prevNode && sub[i] > sz/2) return get_centroid(i, curNode);
        return curNode;
    }
    int max_len; int fine = 0;
    void fill (int curNode, int prevNode, int d, int64_t val1, int64_t val2) {
        dp1[curNode] = val1 = (BASE * val1 + s[curNode]) % MOD;
        dp2[curNode] = val2 = (powr[d] * s[curNode] + val2) % MOD;
        fine += (dp1[curNode] == dp2[curNode] && d + 1 == max_len);
        dp[curNode][0] = prevNode;
        for (int i = 1; i < 17; i++) {
            dp[curNode][i] = dp[dp[curNode][i - 1]][i - 1];
        }
        depth[curNode] = d;
        parent[curNode] = prevNode;
        for (int i: adj[curNode]) {
            if (!hasVisited[i] && i != prevNode) {
                fill(i, curNode, d + 1, val1, val2);
            }
        }
    }

    int64_t go_up (int l, int d) {
        while (d) {
            l = dp[l][(int)floor(log2(d & -d))];
            d -= (d & -d);
        }
        return l;
    }

    int centroid;
    int64_t get (int l, int r) {
        if (depth[l] < depth[r]) {
            return (dp1[r] - (powr[depth[r] - depth[l] + 1] * dp1[parent[l]]) % MOD + MOD) % MOD;
        } else {
            return (((dp2[l] - dp2[parent[r]] + MOD) % MOD) * (ipowr[depth[r]])) % MOD;
        }
    }

    set<int> m1;
    vector<int> to_do;
    void dfs (int curNode, int prevNode) {
        if (depth[curNode] + 1 >= max_len) {
            return;
        }
        to_do.push_back(dp1[curNode]);
        //m1[dp1[curNode]]++, v1[dp1[curNode]]++;
        if (2 * depth[curNode] + 1 >= max_len) {
            if (dp1[go_up(curNode, max_len - depth[curNode] - 1)] == dp2[go_up(curNode, max_len - depth[curNode] - 1)]) {
                int64_t get_val = get(go_up(curNode, max_len - depth[curNode] - 2), curNode) + powr[max_len - depth[curNode] - 1] * s[centroid];
                get_val %= MOD;
                if (m1.count(get_val)) {
                    fine ++;
                    return;
                }
            }
        }
        for (int i: adj[curNode]) {
            if (i != prevNode && !hasVisited[i]) {
                dfs (i, curNode);
            }
        }
    }

    bool solve (int curNode) {
        dfs1(curNode, curNode);
        centroid = get_centroid(curNode, curNode);
        hasVisited[centroid] = true;
        depth[centroid] = 0;
        for (int i = 0; i < 17; i++) dp[centroid][i] = centroid;
        dp1[centroid] = s[centroid], dp2[centroid] = s[centroid];
        fine += (max_len == 1);
        for (int i: adj[centroid]) {
            if (!hasVisited[i]) {
                fill(i, centroid, 1, s[centroid], s[centroid]);
            }
        }
        m1.clear();
        for (int i: adj[centroid]) {
            if (!hasVisited[i]) {
                dfs (i, centroid);
                for (int j: to_do) m1.insert(j);
                to_do.clear();
            }
        }
        if (fine) return true;
        reverse(adj[centroid].begin(), adj[centroid].end());
        m1.clear();
        for (int i: adj[centroid]) {
            if (!hasVisited[i]) {
                dfs (i, centroid);
                for (int j: to_do) m1.insert(j);
                to_do.clear();
            }
        }
        if (fine) return true;
        for (int i: adj[centroid]) {
            if (!hasVisited[i]) {
                if (solve(i)) {
                    return true;
                }
            }
        }
        return false;
    }
    Tree (int n) {
        sub.resize(n), hasVisited.assign(n, false); powr.push_back(1); for (int i = 0; i <= n + 5; i++) powr.push_back(powr.back() * BASE), powr.back() %= MOD;
        ipowr.push_back(1); for (int i = 0; i <= n + 5; i++) ipowr.push_back(ipowr.back() * inv), powr.back() %= MOD;
        parent.resize(n), depth.resize(n), dp1.resize(n), dp2.resize(n);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin >> n;
    string s; cin >> s;
    Tree myTree(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        myTree.adj[u].push_back(v), myTree.adj[v].push_back(u);
    }
    myTree.s = s;
    int myMax = 0;
    int l = 0;
    int r = s.length()/2;
    while (l != r) {
        int m = (l + r + 1)/2;
        myTree.max_len = 2 * m; myTree.fine = 0; myTree.hasVisited.assign(n, false);
        myTree.solve(0);
        if (myTree.fine) {
            l = m;
        } else {
            r = m - 1;
        }
    }
    myMax = max(myMax, 2 * l);
    l = 0;
    r = s.length()/2;
    while (l != r) {
        int m = (l + r + 1)/2;
        myTree.max_len = 2 * m + 1; myTree.fine = 0; myTree.hasVisited.assign(n, false);
        myTree.solve(0);
        if (myTree.fine) {
            l = m;
        } else {
            r = m - 1;
        }
    }
    myMax = max(myMax, 2 * l + 1);
    cout << myMax;
    //cout << inv(BASE) << '\n';
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4820 KB Output is correct
2 Correct 20 ms 4820 KB Output is correct
3 Correct 59 ms 4948 KB Output is correct
4 Correct 58 ms 4948 KB Output is correct
5 Correct 2 ms 4692 KB Output is correct
6 Correct 2 ms 4692 KB Output is correct
7 Correct 2 ms 4736 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3868 ms 12980 KB Output is correct
2 Correct 3903 ms 13140 KB Output is correct
3 Correct 2694 ms 13388 KB Output is correct
4 Correct 3277 ms 13812 KB Output is correct
5 Correct 4679 ms 14228 KB Output is correct
6 Correct 568 ms 12988 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5076 ms 11976 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4820 KB Output is correct
2 Correct 20 ms 4820 KB Output is correct
3 Correct 59 ms 4948 KB Output is correct
4 Correct 58 ms 4948 KB Output is correct
5 Correct 2 ms 4692 KB Output is correct
6 Correct 2 ms 4692 KB Output is correct
7 Correct 2 ms 4736 KB Output is correct
8 Correct 3868 ms 12980 KB Output is correct
9 Correct 3903 ms 13140 KB Output is correct
10 Correct 2694 ms 13388 KB Output is correct
11 Correct 3277 ms 13812 KB Output is correct
12 Correct 4679 ms 14228 KB Output is correct
13 Correct 568 ms 12988 KB Output is correct
14 Execution timed out 5076 ms 11976 KB Time limit exceeded
15 Halted 0 ms 0 KB -