oj.uz

Submission #635862

# Submission time Handle Problem Language Result Execution time Memory
635862 2022-08-27T08:19:25 Z HaYoungJoon Lampice (COCI19_lampice) C++17
110 / 110
 3023 ms 20892 KB 
#include <bits/stdc++.h>
#define ll long long

using namespace std;

typedef pair<int,int> pii;
const int maxn = 5e4 + 1;
const int LOG = 16;
const int base = 31;
const int modu = 1e9 + 7;
int n, pos[maxn], name[2*maxn], numNode, res = 0, timer1 = 0, timer = 0, RMQ[LOG+1][2*maxn], H[maxn], Lg[2*maxn]; ///LCA
char color[maxn];
int child[maxn], root = -1, node[maxn], sta[maxn], fin[maxn];
bool vis[maxn];            ///Centroid
int hashT[maxn], hashN[maxn], POW[maxn], inv_POW[maxn]; ///Hash
vector<int> adj[maxn], adjC[maxn];

#define MIN_HIGH(x,y) (H[name[x]] < H[name[y]] ? (x) : (y))

struct hashFunction
{
  size_t operator()(const pair<int ,
                    int> &x) const
  {
    return x.first ^ x.second;
  }
};

int add(int A, int B) {
    ll tmp = A+B;
    if (tmp >= modu) tmp -= modu;
    if (tmp < 0) tmp += modu;
    return tmp;
}
int mul(int A, int B) {
    ll tmp = 1LL*A*B;
    if (tmp >= modu) tmp %= modu;
    return tmp;
}

void DFS_init(int u, int p) {
    pos[u] = ++timer1;
    name[timer1] = u;
    for (int v: adj[u]) {
        if (v == p) continue;
        H[v] = H[u] + 1;
        hashT[v] = add(color[v], mul(hashT[u],POW[1]));
        hashN[v] = add(mul(color[v],POW[H[v]]),hashN[u]);
        DFS_init(v,u);
        name[++timer1] = u;
        assert(timer1 <= 2*maxn);
    }
}

int LCA(int u, int v) {
    int l = pos[u], r = pos[v];
    if (l > r) swap(l,r);
    int k = Lg[r-l+1];
    return name[MIN_HIGH(RMQ[k][l],RMQ[k][r - (1 << k) + 1])];
}

int binexpo(ll A, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1LL*res*A%modu;
        A = A*A % modu;
        b >>= 1;
    }
    return res;
}
int inv(int A) {
    return binexpo(A,modu-2);
}

int getHash(int u, int v, bool type) {
    int L = LCA(u,v);
    int hash_u = add(add(hashT[u], -mul(hashT[L],POW[H[u] - H[L]] )),mul(color[L],POW[H[u] - H[L]])), hash_v = add(hashN[v],-hashN[L]);
    int target = H[u] - H[L];
    if (H[L] <= target) hash_v = mul(hash_v,POW[target - H[L]]);
    else hash_v = mul(hash_v,inv_POW[H[L] - target]);
    if (type) hash_v = add(hash_v,-mul(color[v],POW[H[u] + H[v] - 2*H[L]]));
    return add(hash_u,hash_v);
}

void DFS_size(int u, int p) {
    child[u] = 1;
    for (int v: adj[u]) {
        if (v == p || vis[v]) continue;
        DFS_size(v,u);
        child[u] += child[v];
    }
}

int get_centroid(int u, int p, int _n) {
    for (int v: adj[u]) {
        if (v == p || vis[v]) continue;
        if (child[v] > _n/2) return get_centroid(v,u,_n);
    }
    return u;
}

void centroid_init(int u, int p) {
    DFS_size(u,u);
    int c = get_centroid(u,u,child[u]);
    vis[c] = 1;
    if (p != -1) adjC[p].push_back(c);
    if (root == -1) root = c;
    for (int v: adj[c]) {
        if (vis[v]) continue;
        centroid_init(v,c);
    }
}

void DFS_centroid(int u) {
    sta[u] = ++timer;
    node[sta[u]] = u;
    for (int v: adjC[u]) {
        DFS_centroid(v);
    }
    fin[u] = timer;
}

void init() {
    POW[0] = 1;
    inv_POW[0] = 1;
    for (int i = 1; i <= n; i++) {
        POW[i] = mul(POW[i-1],base);
        inv_POW[i] = inv(POW[i]);
    }
    hashT[1] = hashN[1] = color[1];
    DFS_init(1,-1);
    for (int i = 1; i <= timer1; i++) RMQ[0][i] = i;
    for (int j = 1; j <= LOG; j++)
        for (int i = 1; i <= timer1 - (1 << j)+1;i++)
        RMQ[j][i] = MIN_HIGH(RMQ[j-1][i],RMQ[j-1][i + (1 << (j-1))]);
    centroid_init(1,-1);
    DFS_centroid(root);
}

bool curAns;

void DFS_ans(int u) {
    vector<pii> tmp;
    unordered_set<pii,hashFunction> st;
    for (int v: adjC[u]) {
        for (int i = sta[v]; i <= fin[v]; i++) {
            int d = H[u] + H[node[i]] - 2*H[LCA(u,node[i])] + 1;
            if (d == numNode) {
                if (getHash(node[i],u,0) == getHash(u,node[i],0)) {
                    curAns = 1;
                    return;
                }
            } else if (d < numNode) {
                int need = add(getHash(node[i],u,1),-mul(getHash(u,node[i],0),POW[numNode - d]));
                if (st.find(pii(numNode - d + 1,need)) != st.end()) {
                    curAns = 1;
                    return;
                }
                tmp.emplace_back(pii(d,need));
            }
        }
        if (v != adj[u].back())
            for (int i = 0; i < tmp.size(); i++) st.insert(tmp[i]);
        tmp.clear();
    }
    st.clear();
    for (int v: adjC[u]) {
        DFS_ans(v);
        if (curAns) return;
    }
}

bool getAns() {
    curAns = 0;
    DFS_ans(root);
    return curAns;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    Lg[0] = -1;
    for (int i = 1; i <= 2*n; i++) Lg[i] = Lg[i/2] + 1;
    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;
        color[i] = c - 'a' + 1;
    }
    for (int i = 1; i < n; i++) {
        int u,v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    init();
    int L = 1, R = n/2, res = 1;
    while (L <= R) {
        int mid = (L + R)/2;
        numNode = 2*mid;
        if (getAns()) {
            res =max(res,2*mid);
            L = mid+1;
        } else R = mid-1;
    }
    L = (res-1)/2; R = (n-1)/2;
    while (L <= R) {
        int mid = (L + R)/2;
        numNode = 2*mid + 1;
        if (getAns()) {
            res = max(res,2*mid+1);
            L = mid+1;
        } else R = mid-1;
    }
    cout << res;
    return 0;
}

Compilation message

lampice.cpp: In function 'void DFS_ans(int)':
lampice.cpp:163:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |             for (int i = 0; i < tmp.size(); i++) st.insert(tmp[i]);
      |                             ~~^~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2772 KB Output is correct
2 Correct 9 ms 2900 KB Output is correct
3 Correct 33 ms 3168 KB Output is correct
4 Correct 32 ms 3276 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1756 ms 18676 KB Output is correct
2 Correct 1820 ms 18980 KB Output is correct
3 Correct 576 ms 19516 KB Output is correct
4 Correct 821 ms 20244 KB Output is correct
5 Correct 2800 ms 20892 KB Output is correct
6 Correct 164 ms 19580 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2301 ms 17600 KB Output is correct
2 Correct 3023 ms 17244 KB Output is correct
3 Correct 2600 ms 17204 KB Output is correct
4 Correct 1947 ms 16640 KB Output is correct
5 Correct 1873 ms 16320 KB Output is correct
6 Correct 1751 ms 14340 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2772 KB Output is correct
2 Correct 9 ms 2900 KB Output is correct
3 Correct 33 ms 3168 KB Output is correct
4 Correct 32 ms 3276 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1756 ms 18676 KB Output is correct
9 Correct 1820 ms 18980 KB Output is correct
10 Correct 576 ms 19516 KB Output is correct
11 Correct 821 ms 20244 KB Output is correct
12 Correct 2800 ms 20892 KB Output is correct
13 Correct 164 ms 19580 KB Output is correct
14 Correct 2301 ms 17600 KB Output is correct
15 Correct 3023 ms 17244 KB Output is correct
16 Correct 2600 ms 17204 KB Output is correct
17 Correct 1947 ms 16640 KB Output is correct
18 Correct 1873 ms 16320 KB Output is correct
19 Correct 1751 ms 14340 KB Output is correct
20 Correct 1412 ms 14016 KB Output is correct
21 Correct 1695 ms 14980 KB Output is correct
22 Correct 2086 ms 15832 KB Output is correct
23 Correct 643 ms 13280 KB Output is correct
24 Correct 2353 ms 15448 KB Output is correct
25 Correct 1588 ms 15232 KB Output is correct
26 Correct 2370 ms 16720 KB Output is correct
27 Correct 2405 ms 16772 KB Output is correct
28 Correct 1598 ms 15220 KB Output is correct
29 Correct 1741 ms 15424 KB Output is correct
30 Correct 1974 ms 16852 KB Output is correct
31 Correct 1585 ms 15308 KB Output is correct
32 Correct 1680 ms 17696 KB Output is correct
33 Correct 1342 ms 16736 KB Output is correct