oj.uz

답안 #530264

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
530264 2022-02-24T22:33:39 Z Alex_tz307 Lampice (COCI19_lampice) C++17
42 / 110
 5000 ms 43776 KB 
#include <bits/stdc++.h>

using namespace std;

const int kN = 5e4;
const int mod = 1e9 + 9;
const int base = 29;
const int kM = (1 << 26) - 1;
string s;
vector<uint16_t> g[1 + kN];
uint16_t sz[1 + kN];
int p[1 + kN], h1[1 + kN], h2[1 + kN];
vector<uint16_t> centroids, nodes;
bitset<1 + kN> vis;
bitset<1 + kM> filter;
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;
  filter[h1[u] & kM] = true;
  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 (filter[hsh & kM] && 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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4556 KB Output is correct
2 Correct 10 ms 5052 KB Output is correct
3 Correct 37 ms 10608 KB Output is correct
4 Correct 46 ms 9292 KB Output is correct
5 Correct 3 ms 4484 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

# 결과 실행 시간 메모리 Grader output
1 Correct 4265 ms 37624 KB Output is correct
2 Correct 2899 ms 37616 KB Output is correct
3 Correct 1728 ms 33312 KB Output is correct
4 Correct 2231 ms 34712 KB Output is correct
5 Correct 4365 ms 43776 KB Output is correct
6 Correct 216 ms 22380 KB Output is correct

Subtask #3
0 / 31.0

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

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4556 KB Output is correct
2 Correct 10 ms 5052 KB Output is correct
3 Correct 37 ms 10608 KB Output is correct
4 Correct 46 ms 9292 KB Output is correct
5 Correct 3 ms 4484 KB Output is correct
6 Correct 2 ms 4428 KB Output is correct
7 Correct 3 ms 4428 KB Output is correct
8 Correct 4265 ms 37624 KB Output is correct
9 Correct 2899 ms 37616 KB Output is correct
10 Correct 1728 ms 33312 KB Output is correct
11 Correct 2231 ms 34712 KB Output is correct
12 Correct 4365 ms 43776 KB Output is correct
13 Correct 216 ms 22380 KB Output is correct
14 Execution timed out 5070 ms 35968 KB Time limit exceeded
15 Halted 0 ms 0 KB -