oj.uz

Submission #530239

# Submission time Handle Problem Language Result Execution time Memory
530239 2022-02-24T20:46:38 Z Alex_tz307 Lampice (COCI19_lampice) C++17
17 / 110
 5000 ms 8740 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_multiset<int> prefs;

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

void modifyPaths(int u, int par, bool t) {
  if (t) {
    prefs.emplace(h1[u]);
  } else {
    prefs.erase(prefs.find(h1[u]));
  }
  for (int v : g[u]) {
    if (!vis[v] && v != par) {
      modifyPaths(v, u, 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 (prefs.count(hsh)) {
        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) {
    prefs.clear();
    dfs1(c, 0, 0);
    for (int v : g[c]) {
      if (!vis[v]) {
        modifyPaths(v, c, false);
        nodes.clear();
        nodes.emplace_back(0);
        nodes.emplace_back(c);
        if (dfs2(v, c, 2, len)) {
          return true;
        }
        modifyPaths(v, c, true);
      }
    }
    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 1740 KB Output is correct
2 Correct 12 ms 1780 KB Output is correct
3 Correct 55 ms 1840 KB Output is correct
4 Correct 62 ms 1868 KB Output is correct
5 Correct 1 ms 1612 KB Output is correct
6 Correct 1 ms 1612 KB Output is correct
7 Correct 2 ms 1692 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5041 ms 7120 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 1740 KB Output is correct
2 Correct 12 ms 1780 KB Output is correct
3 Correct 55 ms 1840 KB Output is correct
4 Correct 62 ms 1868 KB Output is correct
5 Correct 1 ms 1612 KB Output is correct
6 Correct 1 ms 1612 KB Output is correct
7 Correct 2 ms 1692 KB Output is correct
8 Execution timed out 5078 ms 8740 KB Time limit exceeded
9 Halted 0 ms 0 KB -