oj.uz

Submission #546656

# Submission time Handle Problem Language Result Execution time Memory
546656 2022-04-07T23:35:23 Z Olympia Lampice (COCI19_lampice) C++14
110 / 110
 4916 ms 14200 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>
#include <ext/pb_ds/assoc_container.hpp>
 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
 
 
using namespace std;
 
const int MOD = 998244353;
const int BASE = 293;
const int inv = 705244304;
 
 
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)log2(d & -d)];
            d -= (d & -d);
        }
        return l;
    }
 
    int centroid;
 
    __gnu_pbds::gp_hash_table<int, bool> m1;
    vector<int> to_do;
    void dfs (int curNode, int prevNode) {
        if (depth[curNode] + 1 >= max_len) {
            return;
        }
        to_do.push_back(dp1[curNode]);
        for (int i: adj[curNode]) {
            if (i != prevNode && !hasVisited[i]) {
                dfs (i, curNode);
            }
        }
        if (2 * depth[curNode] + 1 >= max_len) {
            int x = go_up(curNode, max_len - depth[curNode] - 2);
            if (dp1[parent[x]] == dp2[parent[x]]) {
                if (m1.find(((dp1[curNode] - (powr[max_len - depth[curNode] - 1] * dp1[parent[x]]) % MOD + MOD) % MOD + powr[max_len - depth[curNode] - 1] * s[centroid]) % MOD) != m1.end()) {
                    fine ++;
                    return;
                }
            }
        }
    }
 
    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[j] = 1;
                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[j] = 1;
                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;
}

Compilation message

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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4820 KB Output is correct
2 Correct 15 ms 4860 KB Output is correct
3 Correct 49 ms 4948 KB Output is correct
4 Correct 50 ms 5020 KB Output is correct
5 Correct 2 ms 4820 KB Output is correct
6 Correct 2 ms 4692 KB Output is correct
7 Correct 2 ms 4692 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2650 ms 13336 KB Output is correct
2 Correct 2157 ms 13480 KB Output is correct
3 Correct 1415 ms 13624 KB Output is correct
4 Correct 1685 ms 13916 KB Output is correct
5 Correct 2624 ms 14200 KB Output is correct
6 Correct 355 ms 12652 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4715 ms 12560 KB Output is correct
2 Correct 4916 ms 12480 KB Output is correct
3 Correct 4336 ms 12692 KB Output is correct
4 Correct 4140 ms 11308 KB Output is correct
5 Correct 3415 ms 12572 KB Output is correct
6 Correct 3403 ms 12144 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4820 KB Output is correct
2 Correct 15 ms 4860 KB Output is correct
3 Correct 49 ms 4948 KB Output is correct
4 Correct 50 ms 5020 KB Output is correct
5 Correct 2 ms 4820 KB Output is correct
6 Correct 2 ms 4692 KB Output is correct
7 Correct 2 ms 4692 KB Output is correct
8 Correct 2650 ms 13336 KB Output is correct
9 Correct 2157 ms 13480 KB Output is correct
10 Correct 1415 ms 13624 KB Output is correct
11 Correct 1685 ms 13916 KB Output is correct
12 Correct 2624 ms 14200 KB Output is correct
13 Correct 355 ms 12652 KB Output is correct
14 Correct 4715 ms 12560 KB Output is correct
15 Correct 4916 ms 12480 KB Output is correct
16 Correct 4336 ms 12692 KB Output is correct
17 Correct 4140 ms 11308 KB Output is correct
18 Correct 3415 ms 12572 KB Output is correct
19 Correct 3403 ms 12144 KB Output is correct
20 Correct 2368 ms 10684 KB Output is correct
21 Correct 2785 ms 12208 KB Output is correct
22 Correct 3792 ms 12276 KB Output is correct
23 Correct 1032 ms 9364 KB Output is correct
24 Correct 3454 ms 10512 KB Output is correct
25 Correct 3336 ms 10400 KB Output is correct
26 Correct 4269 ms 13308 KB Output is correct
27 Correct 4349 ms 12840 KB Output is correct
28 Correct 2624 ms 9500 KB Output is correct
29 Correct 2828 ms 9708 KB Output is correct
30 Correct 3149 ms 10992 KB Output is correct
31 Correct 3270 ms 10396 KB Output is correct
32 Correct 2585 ms 11992 KB Output is correct
33 Correct 2265 ms 12524 KB Output is correct