oj.uz

Submission #546608

# Submission time Handle Problem Language Result Execution time Memory
546608 2022-04-07T21:19:45 Z Olympia Lampice (COCI19_lampice) C++17
42 / 110
 5000 ms 32028 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 ("Ofast")
#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<int> adj[(int)4e5];;
    vector<int64_t> powr, ipowr;
    vector<int> dp[(int)4e5];
    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][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; bool exit = false;
    void dfs (int curNode, int prevNode) { if (exit) return;
        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)) { exit = true;
                    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();
            }
        }
        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);
        for (int i = 0; i < n; i++) dp[i].resize(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.exit = 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.exit = 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 ("Ofast")
      | 
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 17 ms 19156 KB Output is correct
2 Correct 30 ms 19156 KB Output is correct
3 Correct 67 ms 19416 KB Output is correct
4 Correct 76 ms 19484 KB Output is correct
5 Correct 15 ms 19028 KB Output is correct
6 Correct 13 ms 19100 KB Output is correct
7 Correct 14 ms 19064 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3986 ms 30320 KB Output is correct
2 Correct 3911 ms 30568 KB Output is correct
3 Correct 2830 ms 30884 KB Output is correct
4 Correct 3285 ms 31544 KB Output is correct
5 Correct 4749 ms 32028 KB Output is correct
6 Correct 648 ms 30856 KB Output is correct

Subtask #3
0 / 31.0

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

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19156 KB Output is correct
2 Correct 30 ms 19156 KB Output is correct
3 Correct 67 ms 19416 KB Output is correct
4 Correct 76 ms 19484 KB Output is correct
5 Correct 15 ms 19028 KB Output is correct
6 Correct 13 ms 19100 KB Output is correct
7 Correct 14 ms 19064 KB Output is correct
8 Correct 3986 ms 30320 KB Output is correct
9 Correct 3911 ms 30568 KB Output is correct
10 Correct 2830 ms 30884 KB Output is correct
11 Correct 3285 ms 31544 KB Output is correct
12 Correct 4749 ms 32028 KB Output is correct
13 Correct 648 ms 30856 KB Output is correct
14 Execution timed out 5041 ms 30044 KB Time limit exceeded
15 Halted 0 ms 0 KB -