oj.uz

답안 #530833

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
530833 2022-02-26T22:28:55 Z Alex_tz307 Lampice (COCI19_lampice) C++17
110 / 110
 3169 ms 13888 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

using namespace std;

const int kN = 5e4;
const int mod = 1e9 + 7;
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) {
  preffixes[depth].erase(preffixes[depth].find(h1[u]));
  for (int v : g[u]) {
    if (!vis[v] && v != par) {
      removePaths(v, u, depth + 1);
    }
  }
}

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);
        m = 0;
        nodes[m++] = 0;
        nodes[m++] = c;
        if (dfs2(v, c, 2)) {
          addPaths(v, c, 2);
          removePaths(c, 0, 1);
          return true;
        }
        addPaths(v, c, 2);
      }
    }
    removePaths(c, 0, 1);
  }
  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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4428 KB Output is correct
2 Correct 5 ms 4428 KB Output is correct
3 Correct 17 ms 4616 KB Output is correct
4 Correct 17 ms 4684 KB Output is correct
5 Correct 3 ms 4428 KB Output is correct
6 Correct 3 ms 4428 KB Output is correct
7 Correct 4 ms 4428 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1724 ms 12600 KB Output is correct
2 Correct 482 ms 12884 KB Output is correct
3 Correct 386 ms 13048 KB Output is correct
4 Correct 469 ms 13508 KB Output is correct
5 Correct 671 ms 13888 KB Output is correct
6 Correct 273 ms 13888 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3169 ms 10388 KB Output is correct
2 Correct 1487 ms 9920 KB Output is correct
3 Correct 1845 ms 10564 KB Output is correct
4 Correct 796 ms 10816 KB Output is correct
5 Correct 910 ms 9412 KB Output is correct
6 Correct 1608 ms 9224 KB Output is correct

Subtask #4
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4428 KB Output is correct
2 Correct 5 ms 4428 KB Output is correct
3 Correct 17 ms 4616 KB Output is correct
4 Correct 17 ms 4684 KB Output is correct
5 Correct 3 ms 4428 KB Output is correct
6 Correct 3 ms 4428 KB Output is correct
7 Correct 4 ms 4428 KB Output is correct
8 Correct 1724 ms 12600 KB Output is correct
9 Correct 482 ms 12884 KB Output is correct
10 Correct 386 ms 13048 KB Output is correct
11 Correct 469 ms 13508 KB Output is correct
12 Correct 671 ms 13888 KB Output is correct
13 Correct 273 ms 13888 KB Output is correct
14 Correct 3169 ms 10388 KB Output is correct
15 Correct 1487 ms 9920 KB Output is correct
16 Correct 1845 ms 10564 KB Output is correct
17 Correct 796 ms 10816 KB Output is correct
18 Correct 910 ms 9412 KB Output is correct
19 Correct 1608 ms 9224 KB Output is correct
20 Correct 343 ms 8904 KB Output is correct
21 Correct 405 ms 9128 KB Output is correct
22 Correct 825 ms 9208 KB Output is correct
23 Correct 160 ms 9152 KB Output is correct
24 Correct 836 ms 9928 KB Output is correct
25 Correct 1114 ms 9788 KB Output is correct
26 Correct 1709 ms 10692 KB Output is correct
27 Correct 2679 ms 9496 KB Output is correct
28 Correct 268 ms 9408 KB Output is correct
29 Correct 244 ms 9540 KB Output is correct
30 Correct 805 ms 10776 KB Output is correct
31 Correct 1202 ms 9784 KB Output is correct
32 Correct 601 ms 11240 KB Output is correct
33 Correct 208 ms 9228 KB Output is correct