oj.uz

답안 #530119

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
530119 2022-02-24T16:10:10 Z Alex_tz307 Lampice (COCI19_lampice) C++17
0 / 110
 5000 ms 9044 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 invBase, 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);
  }
  invBase = invers(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;
  bool ok = true;
  if (depth < d) {
    ok = false;
  }
  int split = nodes[nodes.size() - d - 1];
  if (ok) {
    int hsh = add(h1[u], mod - mult(p[d], h1[split]));
    if (!prefs.count(hsh)) {
      ok = false;
    }
  }
  if (ok) {
    int mid = len - 2 * d;
    if (mid == 0) {
      return true;
    }
    if (h1[split] == h2[split]) {
      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;
  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;
    }
  }
  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 * l - 1;
  l = 2, 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 + ok2, ret, 2 * (l - 1)}) << '\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
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 1744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5038 ms 9044 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5023 ms 7632 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 1744 KB Output isn't correct
2 Halted 0 ms 0 KB -