oj.uz

답안 #546652

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
546652 2022-04-07T23:31:26 Z Olympia Lampice (COCI19_lampice) C++14
42 / 110
 5000 ms 14352 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>


using namespace std;

const int MOD = 998244353;
const int BASE = 293;
const int inv = 705244304;

int64_t binPow (int64_t x, int64_t y) {
    int64_t ans = 1; int64_t res = x;
    while (y) {
        if (y & 1) {
            ans *= res, ans %= MOD;
        }
        res *= res, res %= MOD;
        y /= 2;
    }
    return ans;
}


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

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4820 KB Output is correct
2 Correct 14 ms 4900 KB Output is correct
3 Correct 51 ms 5036 KB Output is correct
4 Correct 56 ms 5028 KB Output is correct
5 Correct 2 ms 4692 KB Output is correct
6 Correct 2 ms 4692 KB Output is correct
7 Correct 3 ms 4692 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2750 ms 13340 KB Output is correct
2 Correct 2244 ms 13592 KB Output is correct
3 Correct 1470 ms 13688 KB Output is correct
4 Correct 1757 ms 14060 KB Output is correct
5 Correct 2761 ms 14352 KB Output is correct
6 Correct 315 ms 12588 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5028 ms 12660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4820 KB Output is correct
2 Correct 14 ms 4900 KB Output is correct
3 Correct 51 ms 5036 KB Output is correct
4 Correct 56 ms 5028 KB Output is correct
5 Correct 2 ms 4692 KB Output is correct
6 Correct 2 ms 4692 KB Output is correct
7 Correct 3 ms 4692 KB Output is correct
8 Correct 2750 ms 13340 KB Output is correct
9 Correct 2244 ms 13592 KB Output is correct
10 Correct 1470 ms 13688 KB Output is correct
11 Correct 1757 ms 14060 KB Output is correct
12 Correct 2761 ms 14352 KB Output is correct
13 Correct 315 ms 12588 KB Output is correct
14 Execution timed out 5028 ms 12660 KB Time limit exceeded
15 Halted 0 ms 0 KB -