oj.uz

Submission #530131

# Submission time Handle Problem Language Result Execution time Memory
530131 2022-02-24T16:35:46 Z Alex_tz307 Lampice (COCI19_lampice) C++17
0 / 110
 5000 ms 9052 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];
bitset<1 + kN> vis;
unordered_multiset<int> prefs;
vector<int> nodes;

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;
}

int Pow(int x, int n) {
  int ans = 1;
  while (n) {
    if (n & 1) {
      multSelf(ans, x);
    }
    multSelf(x, x);
    n >>= 1;
  }
  return ans;
}

int invers(int x) {
  return Pow(x, mod - 2);
}

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

bool dfs2(int u, int par, int depth, int len) {
  if (depth == len + 1) {
    return false;
  }
  nodes.emplace_back(u);
  prefs.erase(prefs.find(add(h1[u], mod - mult(p[depth - 1], h1[nodes[1]]))));
  int d = len - depth;
  int split = nodes[nodes.size() - d - 1];
  if (d <= depth && h1[split] == h2[split]) {
    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;
    }
  }
  prefs.emplace(add(h1[u], mod - mult(p[depth - 1], h1[nodes[1]])));
  nodes.pop_back();
  return false;
}

bool solve(int u, int len) {
  findSize(u, 0);
  int c = findCentroid(u, 0, sz[u]);
  prefs.clear();
  dfs1(c, c, 0, 0);
  nodes.clear();
  nodes.emplace_back(0);
  if (dfs2(c, 0, 1, len)) {
    return true;
  }
  vis[c] = true;
  for (int v : g[c]) {
    if (!vis[v] && solve(v, len)) {
      return 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;
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  int l = 1, r = (n - 1) / 2;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (check(n, 2 * mid + 1)) {
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  int ret = 2 * r + 1;
  l = 1, r = n / 2;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (check(n, 2 * mid)) {
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  cout << max(1, 2 * r) << '\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;
}

Compilation message

lampice.cpp: In function 'void testCase()':
lampice.cpp:159:7: warning: unused variable 'ret' [-Wunused-variable]
  159 |   int ret = 2 * r + 1;
      |       ^~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1612 KB Output is correct
2 Correct 15 ms 1696 KB Output is correct
3 Correct 54 ms 1844 KB Output is correct
4 Incorrect 75 ms 1872 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5049 ms 9052 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 5046 ms 7548 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 1612 KB Output is correct
2 Correct 15 ms 1696 KB Output is correct
3 Correct 54 ms 1844 KB Output is correct
4 Incorrect 75 ms 1872 KB Output isn't correct
5 Halted 0 ms 0 KB -