oj.uz

Submission #635859

# Submission time Handle Problem Language Result Execution time Memory
635859 2022-08-27T08:13:10 Z HaYoungJoon Lampice (COCI19_lampice) C++17
73 / 110
 3248 ms 20816 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;
    }
}

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/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:162: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]
  162 |             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 10 ms 2900 KB Output is correct
3 Correct 34 ms 3160 KB Output is correct
4 Correct 42 ms 3276 KB Output is correct
5 Correct 2 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 1845 ms 18644 KB Output is correct
2 Correct 2084 ms 19024 KB Output is correct
3 Correct 699 ms 19460 KB Output is correct
4 Correct 946 ms 20136 KB Output is correct
5 Correct 3173 ms 20816 KB Output is correct
6 Correct 167 ms 19552 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2892 ms 17592 KB Output is correct
2 Correct 3248 ms 17332 KB Output is correct
3 Correct 2707 ms 17244 KB Output is correct
4 Correct 2172 ms 16744 KB Output is correct
5 Correct 1953 ms 16236 KB Output is correct
6 Correct 1904 ms 14428 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2772 KB Output is correct
2 Correct 10 ms 2900 KB Output is correct
3 Correct 34 ms 3160 KB Output is correct
4 Correct 42 ms 3276 KB Output is correct
5 Correct 2 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 1845 ms 18644 KB Output is correct
9 Correct 2084 ms 19024 KB Output is correct
10 Correct 699 ms 19460 KB Output is correct
11 Correct 946 ms 20136 KB Output is correct
12 Correct 3173 ms 20816 KB Output is correct
13 Correct 167 ms 19552 KB Output is correct
14 Correct 2892 ms 17592 KB Output is correct
15 Correct 3248 ms 17332 KB Output is correct
16 Correct 2707 ms 17244 KB Output is correct
17 Correct 2172 ms 16744 KB Output is correct
18 Correct 1953 ms 16236 KB Output is correct
19 Correct 1904 ms 14428 KB Output is correct
20 Correct 1657 ms 13876 KB Output is correct
21 Correct 1848 ms 14940 KB Output is correct
22 Correct 2267 ms 15740 KB Output is correct
23 Correct 661 ms 13240 KB Output is correct
24 Correct 2529 ms 15444 KB Output is correct
25 Correct 1764 ms 15132 KB Output is correct
26 Correct 2643 ms 16776 KB Output is correct
27 Incorrect 2548 ms 16768 KB Output isn't correct
28 Halted 0 ms 0 KB -