oj.uz

Submission #530835

# Submission time Handle Problem Language Result Execution time Memory
530835 2022-02-26T22:41:42 Z Alex_tz307 Lampice (COCI19_lampice) C++17
110 / 110
 3025 ms 14720 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 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, bool flag) {
  if (flag || preffixes[depth].count(h1[u])) {
    preffixes[depth].erase(preffixes[depth].find(h1[u]));
  }
  for (int v : g[u]) {
    if (!vis[v] && v != par) {
      removePaths(v, u, depth + 1, flag);
    }
  }
}

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, true);
        m = 0;
        nodes[m++] = 0;
        nodes[m++] = c;
        if (dfs2(v, c, 2)) {
          removePaths(c, 0, 1, false);
          return true;
        }
        addPaths(v, c, 2);
      }
    }
    removePaths(c, 0, 1, true);
  }
  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 3 ms 4488 KB Output is correct
2 Correct 5 ms 4428 KB Output is correct
3 Correct 16 ms 4612 KB Output is correct
4 Correct 17 ms 4704 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 4428 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1799 ms 13368 KB Output is correct
2 Correct 444 ms 13504 KB Output is correct
3 Correct 406 ms 13792 KB Output is correct
4 Correct 412 ms 14276 KB Output is correct
5 Correct 709 ms 14720 KB Output is correct
6 Correct 285 ms 14676 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3025 ms 10412 KB Output is correct
2 Correct 1600 ms 9888 KB Output is correct
3 Correct 1794 ms 10532 KB Output is correct
4 Correct 1091 ms 10744 KB Output is correct
5 Correct 1053 ms 9548 KB Output is correct
6 Correct 1617 ms 9236 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4488 KB Output is correct
2 Correct 5 ms 4428 KB Output is correct
3 Correct 16 ms 4612 KB Output is correct
4 Correct 17 ms 4704 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 4428 KB Output is correct
8 Correct 1799 ms 13368 KB Output is correct
9 Correct 444 ms 13504 KB Output is correct
10 Correct 406 ms 13792 KB Output is correct
11 Correct 412 ms 14276 KB Output is correct
12 Correct 709 ms 14720 KB Output is correct
13 Correct 285 ms 14676 KB Output is correct
14 Correct 3025 ms 10412 KB Output is correct
15 Correct 1600 ms 9888 KB Output is correct
16 Correct 1794 ms 10532 KB Output is correct
17 Correct 1091 ms 10744 KB Output is correct
18 Correct 1053 ms 9548 KB Output is correct
19 Correct 1617 ms 9236 KB Output is correct
20 Correct 307 ms 8936 KB Output is correct
21 Correct 357 ms 9008 KB Output is correct
22 Correct 765 ms 9112 KB Output is correct
23 Correct 166 ms 9152 KB Output is correct
24 Correct 703 ms 9988 KB Output is correct
25 Correct 1070 ms 9932 KB Output is correct
26 Correct 1654 ms 10644 KB Output is correct
27 Correct 2654 ms 9512 KB Output is correct
28 Correct 252 ms 9408 KB Output is correct
29 Correct 261 ms 9452 KB Output is correct
30 Correct 1054 ms 10816 KB Output is correct
31 Correct 1010 ms 9724 KB Output is correct
32 Correct 613 ms 11556 KB Output is correct
33 Correct 189 ms 9252 KB Output is correct