oj.uz

Submission #546589

# Submission time Handle Problem Language Result Execution time Memory
546589 2022-04-07T20:59:10 Z Olympia Lampice (COCI19_lampice) C++17
17 / 110
 5000 ms 16100 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>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

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<vector<int>> adj;
    vector<int64_t> powr, ipowr;
    vector<vector<int>> dp;
    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) {
        if (d == 0) {
            return l;
        }
        int lg2 = log2(d);
        return go_up(dp[l][lg2], d - (1 << lg2));
    }

    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;
        dp[centroid].assign(dp[centroid].size(), 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), adj.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), dp.assign(n, (vector<int>)(17));
    }
};

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';
}

Compilation message

lampice.cpp:17: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   17 | #pragma GCC optimization ("O3")
      | 
lampice.cpp:18: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   18 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 15 ms 512 KB Output is correct
3 Correct 58 ms 724 KB Output is correct
4 Correct 61 ms 824 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3849 ms 13872 KB Output is correct
2 Correct 3805 ms 14408 KB Output is correct
3 Correct 2741 ms 14792 KB Output is correct
4 Correct 3312 ms 15508 KB Output is correct
5 Execution timed out 5056 ms 16100 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

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

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 15 ms 512 KB Output is correct
3 Correct 58 ms 724 KB Output is correct
4 Correct 61 ms 824 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 3849 ms 13872 KB Output is correct
9 Correct 3805 ms 14408 KB Output is correct
10 Correct 2741 ms 14792 KB Output is correct
11 Correct 3312 ms 15508 KB Output is correct
12 Execution timed out 5056 ms 16100 KB Time limit exceeded
13 Halted 0 ms 0 KB -