oj.uz

Submission #530832

# Submission time Handle Problem Language Result Execution time Memory
530832 2022-02-26T22:23:45 Z Alex_tz307 Lampice (COCI19_lampice) C++17
110 / 110
 2919 ms 14724 KB 
#include <bits/stdc++.h>

using namespace std;

const int kN = 5e4;
const int mod = 1e9 + 7;
const int base = 29;
string s;
vector<int> g[1 + kN];
int len, m, p[1 + kN], sz[1 + kN], dp[1 + kN], best[1 + kN], h1[1 + kN], h2[1 + kN], nodes[1 + kN];
vector<int> centroids;
bitset<1 + kN> vis;
unordered_multiset<int> preffixes[kN];

int add(int x, int y) {
  x += y;
  if (x >= mod) {
    return x - mod;
  }
  return x;
}

int mult(int x, int y) {
  return (int64_t)x * y % mod;
}

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 dfs(int u, int par) {
  int mx1 = 0, mx2 = 0;
  for (int v : g[u]) {
    if (!vis[v] && v != par) {
      dfs(v, u);
      if (mx1 < dp[v]) {
        mx2 = mx1;
        mx1 = dp[v];
      } else if (mx2 < dp[v]) {
        mx2 = dp[v];
      }
    }
  }
  dp[u] = mx1 + 1;
  best[u] = mx1 + mx2 + 1;
}

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

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].emplace(h1[u]);
  for (int v : g[u]) {
    if (!vis[v] && v != par) {
      dfs1(v, u, depth + 1);
    }
  }
}

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

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

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

bool solve(int u) {
  for (int c : centroids) {
    vis[c] = true;
    if (best[c] < len) {
      continue;
    }
    dfs1(c, 0, 0);
    for (int v : g[c]) {
      if (!vis[v]) {
        removePaths(v, c, 2);
        m = 0;
        nodes[m++] = 0;
        nodes[m++] = c;
        if (dfs2(v, c, 2)) {
          addPaths(v, c, 2);
          removePaths(c, 0, 1);
          return true;
        }
        addPaths(v, c, 2);
      }
    }
    removePaths(c, 0, 1);
  }
  return false;
}

bool check(int n) {
  bool ret = solve(1);
  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;
    len = 2 * mid + 1;
    if (check(n)) {
      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;
    len = 2 * mid;
    if (check(n)) {
      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 4 ms 4428 KB Output is correct
2 Correct 5 ms 4428 KB Output is correct
3 Correct 17 ms 4556 KB Output is correct
4 Correct 17 ms 4708 KB Output is correct
5 Correct 3 ms 4428 KB Output is correct
6 Correct 3 ms 4428 KB Output is correct
7 Correct 4 ms 4428 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1645 ms 13312 KB Output is correct
2 Correct 479 ms 13504 KB Output is correct
3 Correct 438 ms 13768 KB Output is correct
4 Correct 511 ms 14276 KB Output is correct
5 Correct 708 ms 14724 KB Output is correct
6 Correct 278 ms 14672 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2919 ms 10452 KB Output is correct
2 Correct 1426 ms 10556 KB Output is correct
3 Correct 1583 ms 11076 KB Output is correct
4 Correct 761 ms 11376 KB Output is correct
5 Correct 818 ms 10084 KB Output is correct
6 Correct 1445 ms 9824 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4428 KB Output is correct
2 Correct 5 ms 4428 KB Output is correct
3 Correct 17 ms 4556 KB Output is correct
4 Correct 17 ms 4708 KB Output is correct
5 Correct 3 ms 4428 KB Output is correct
6 Correct 3 ms 4428 KB Output is correct
7 Correct 4 ms 4428 KB Output is correct
8 Correct 1645 ms 13312 KB Output is correct
9 Correct 479 ms 13504 KB Output is correct
10 Correct 438 ms 13768 KB Output is correct
11 Correct 511 ms 14276 KB Output is correct
12 Correct 708 ms 14724 KB Output is correct
13 Correct 278 ms 14672 KB Output is correct
14 Correct 2919 ms 10452 KB Output is correct
15 Correct 1426 ms 10556 KB Output is correct
16 Correct 1583 ms 11076 KB Output is correct
17 Correct 761 ms 11376 KB Output is correct
18 Correct 818 ms 10084 KB Output is correct
19 Correct 1445 ms 9824 KB Output is correct
20 Correct 306 ms 9576 KB Output is correct
21 Correct 330 ms 9548 KB Output is correct
22 Correct 778 ms 9688 KB Output is correct
23 Correct 158 ms 9684 KB Output is correct
24 Correct 736 ms 10564 KB Output is correct
25 Correct 999 ms 10484 KB Output is correct
26 Correct 1508 ms 11200 KB Output is correct
27 Correct 2493 ms 10192 KB Output is correct
28 Correct 243 ms 10004 KB Output is correct
29 Correct 237 ms 10116 KB Output is correct
30 Correct 845 ms 11420 KB Output is correct
31 Correct 1024 ms 10304 KB Output is correct
32 Correct 594 ms 12224 KB Output is correct
33 Correct 159 ms 9884 KB Output is correct