oj.uz

Submission #530262

# Submission time Handle Problem Language Result Execution time Memory
530262 2022-02-24T22:25:24 Z Alex_tz307 Lampice (COCI19_lampice) C++17
42 / 110
 5000 ms 35040 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, 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;
  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 10 ms 4520 KB Output is correct
3 Correct 35 ms 4812 KB Output is correct
4 Correct 44 ms 4684 KB Output is correct
5 Correct 3 ms 4428 KB Output is correct
6 Correct 2 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 3811 ms 30112 KB Output is correct
2 Correct 2664 ms 28996 KB Output is correct
3 Correct 1547 ms 24620 KB Output is correct
4 Correct 1940 ms 26032 KB Output is correct
5 Correct 3874 ms 35040 KB Output is correct
6 Correct 159 ms 13696 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5069 ms 27996 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 10 ms 4520 KB Output is correct
3 Correct 35 ms 4812 KB Output is correct
4 Correct 44 ms 4684 KB Output is correct
5 Correct 3 ms 4428 KB Output is correct
6 Correct 2 ms 4428 KB Output is correct
7 Correct 3 ms 4428 KB Output is correct
8 Correct 3811 ms 30112 KB Output is correct
9 Correct 2664 ms 28996 KB Output is correct
10 Correct 1547 ms 24620 KB Output is correct
11 Correct 1940 ms 26032 KB Output is correct
12 Correct 3874 ms 35040 KB Output is correct
13 Correct 159 ms 13696 KB Output is correct
14 Execution timed out 5069 ms 27996 KB Time limit exceeded
15 Halted 0 ms 0 KB -