oj.uz

Submission #530263

# Submission time Handle Problem Language Result Execution time Memory
530263 2022-02-24T22:29:15 Z Alex_tz307 Lampice (COCI19_lampice) C++17
42 / 110
 5000 ms 68292 KB 
#include <bits/stdc++.h>

using namespace std;

const int kN = 5e4;
const int mod = 1e9 + 9;
const int base = 29;
const int kM = (1 << 28) - 1;
string s;
vector<uint16_t> g[1 + kN];
uint16_t sz[1 + kN];
int p[1 + kN], h1[1 + kN], h2[1 + kN];
vector<uint16_t> centroids, nodes;
bitset<1 + kN> vis;
bitset<1 + kM> filter;
unordered_map<int, uint16_t> preffixes[kN];

void addSelf(int &x, const int &y) {
  x += y;
  if (x >= mod) {
    x -= mod;
  }
}

int add(int x, const int &y) {
  addSelf(x, y);
  return x;
}

void multSelf(int &x, const int &y) {
  x = (int64_t)x * y % mod;
}

int mult(int x, const int &y) {
  multSelf(x, y);
  return x;
}

void precalc() {
  p[0] = 1;
  for (int i = 1; i <= kN; ++i) {
    p[i] = mult(p[i - 1], base);
  }
}

void findSize(int u, int par) {
  sz[u] = 1;
  for (int v : g[u]) {
    if (!vis[v] && v != par) {
      findSize(v, u);
      sz[u] += sz[v];
    }
  }
}

int findCentroid(int u, int par, int n) {
  for (int v : g[u]) {
    if (!vis[v] && v != par && sz[v] > n / 2) {
      return findCentroid(v, u, n);
    }
  }
  return u;
}

void dfs1(int u, int par, int depth) {
  h1[u] = add(mult(h1[par], base), s[u] - 'a' + 1);
  h2[u] = add(h2[par], mult(p[depth], s[u] - 'a' + 1));
  preffixes[depth + 1][h1[u]] += 1;
  filter[h1[u] & kM] = true;
  for (int v : g[u]) {
    if (!vis[v] && v != par) {
      dfs1(v, u, depth + 1);
    }
  }
}

void modifyPaths(int u, int par, int depth, int t) {
  preffixes[depth][h1[u]] += t;
  for (int v : g[u]) {
    if (!vis[v] && v != par) {
      modifyPaths(v, u, depth + 1, t);
    }
  }
}

bool dfs2(int u, int par, int depth, int len) {
  if (depth == len) {
    return h1[u] == h2[u];
  }
  nodes.emplace_back(u);
  int d = len - depth + 1;
  if (d <= depth) {
    int split = nodes[nodes.size() - d];
    if (h1[split] == h2[split]) {
      split = nodes[nodes.size() - d - 1];
      int hsh = add(h1[u], mod - mult(p[d], h1[split]));
      if (filter[hsh & kM] && preffixes[d][hsh] > 0) {
        return true;
      }
    }
  }
  for (int v : g[u]) {
    if (!vis[v] && v != par && dfs2(v, u, depth + 1, len)) {
      return true;
    }
  }
  nodes.pop_back();
  return false;
}

void build(int u) {
  findSize(u, 0);
  int c = findCentroid(u, 0, sz[u]);
  centroids.emplace_back(c);
  vis[c] = true;
  for (int v : g[c]) {
    if (!vis[v]) {
      build(v);
    }
  }
}

bool solve(int u, int len) {
  for (int c : centroids) {
    dfs1(c, 0, 0);
    for (int v : g[c]) {
      if (!vis[v]) {
        modifyPaths(v, c, 2, -1);
        nodes.clear();
        nodes.emplace_back(0);
        nodes.emplace_back(c);
        if (dfs2(v, c, 2, len)) {
          modifyPaths(v, c, 2, 1);
          modifyPaths(c, 0, 1, -1);
          return true;
        }
        modifyPaths(v, c, 2, 1);
      }
    }
    modifyPaths(c, 0, 1, -1);
    vis[c] = true;
  }
  return false;
}

bool check(int n, int len) {
  bool ret = solve(1, len);
  for (int v = 1; v <= n; ++v) {
    vis[v] = false;
  }
  return ret;
}

void testCase() {
  int n;
  cin >> n >> s;
  s = '$' + s;
  bool ok2 = false;
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
    if (s[u] == s[v]) {
      ok2 = true;
    }
  }
  build(1);
  for (int v = 1; v <= n; ++v) {
    vis[v] = false;
  }
  int l = 1, r = (n - 1) / 2, ans1 = 1;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (check(n, 2 * mid + 1)) {
      ans1 = 2 * mid + 1;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  int ans2 = 0;
  l = 2, r = n / 2;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (check(n, 2 * mid)) {
      ans2 = 2 * mid;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  cout << max({1 + ok2, ans1, ans2}) << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  precalc();
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4684 KB Output is correct
2 Correct 11 ms 5068 KB Output is correct
3 Correct 48 ms 13260 KB Output is correct
4 Correct 58 ms 10956 KB Output is correct
5 Correct 3 ms 4428 KB Output is correct
6 Correct 3 ms 4428 KB Output is correct
7 Correct 2 ms 4428 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4316 ms 62248 KB Output is correct
2 Correct 3124 ms 62456 KB Output is correct
3 Correct 1845 ms 57960 KB Output is correct
4 Correct 2196 ms 59332 KB Output is correct
5 Correct 4279 ms 68292 KB Output is correct
6 Correct 273 ms 45380 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5028 ms 60544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4684 KB Output is correct
2 Correct 11 ms 5068 KB Output is correct
3 Correct 48 ms 13260 KB Output is correct
4 Correct 58 ms 10956 KB Output is correct
5 Correct 3 ms 4428 KB Output is correct
6 Correct 3 ms 4428 KB Output is correct
7 Correct 2 ms 4428 KB Output is correct
8 Correct 4316 ms 62248 KB Output is correct
9 Correct 3124 ms 62456 KB Output is correct
10 Correct 1845 ms 57960 KB Output is correct
11 Correct 2196 ms 59332 KB Output is correct
12 Correct 4279 ms 68292 KB Output is correct
13 Correct 273 ms 45380 KB Output is correct
14 Execution timed out 5028 ms 60544 KB Time limit exceeded
15 Halted 0 ms 0 KB -