Submission #635862

#	Time	Username	Problem	Language	Result	Execution time	Memory
635862		HaYoungJoon	Lampice (COCI19_lampice)	C++17	110 / 110	3023 ms	20892 KiB

lampice

#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 (stderr)

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 / 17
• Subtask 2: 25 / 25
• Subtask 3: 31 / 31
• Subtask 4: 37 / 37