oj.uz

Submission #530258

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

using namespace std;

const int kN = 5e4;
const int mod = 1e9 + 9;
const int base = 29;
string s;
vector<int> g[1 + kN];
int p[1 + kN], sz[1 + kN], h1[1 + kN], h2[1 + kN];
vector<int> centroids, nodes;
bitset<1 + kN> vis;
unordered_map<int, int> 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;
  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 (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 5 ms 4428 KB Output is correct
2 Correct 12 ms 4508 KB Output is correct
3 Correct 36 ms 4820 KB Output is correct
4 Correct 44 ms 4684 KB Output is correct
5 Correct 3 ms 4428 KB Output is correct
6 Correct 3 ms 4428 KB Output is correct
7 Correct 3 ms 4420 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4156 ms 29924 KB Output is correct
2 Correct 2802 ms 28996 KB Output is correct
3 Correct 1624 ms 24620 KB Output is correct
4 Correct 2120 ms 26132 KB Output is correct
5 Correct 4113 ms 35044 KB Output is correct
6 Correct 162 ms 13696 KB Output is correct

Subtask #3
0 / 31.0

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

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4428 KB Output is correct
2 Correct 12 ms 4508 KB Output is correct
3 Correct 36 ms 4820 KB Output is correct
4 Correct 44 ms 4684 KB Output is correct
5 Correct 3 ms 4428 KB Output is correct
6 Correct 3 ms 4428 KB Output is correct
7 Correct 3 ms 4420 KB Output is correct
8 Correct 4156 ms 29924 KB Output is correct
9 Correct 2802 ms 28996 KB Output is correct
10 Correct 1624 ms 24620 KB Output is correct
11 Correct 2120 ms 26132 KB Output is correct
12 Correct 4113 ms 35044 KB Output is correct
13 Correct 162 ms 13696 KB Output is correct
14 Execution timed out 5060 ms 28172 KB Time limit exceeded
15 Halted 0 ms 0 KB -