oj.uz

답안 #530257

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

using namespace std;

const int kN = 5e4;
const int mod = 1e9 + 9;
const int base = 29;
const int MASK = (1 << 28) - 1;
const int hmod = 393241;
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;
bitset<1 + MASK> filter;

typedef struct element {
  int val, cnt;
  element *next;
} *lista;

lista h[hmod];

void add(int x) {
  filter[x & MASK] = true;
  int key = x % hmod;
  lista p;
  for (p = h[key]; p; p = p->next) {
    if (p->val == x) {
      p->cnt += 1;
      return;
    }
  }
  p = new element;
  p->val = x;
  p->cnt = 1;
  p->next = h[key];
  h[key] = p;
}

void rem(int x) {
  if (!filter[x & MASK]) {
    return;
  }
  int key = x % hmod;
  for (lista p = h[key]; p; p = p->next) {
    if (p->val == x) {
      p->cnt -= 1;
      return;
    }
  }
}

bool ok(int x) {
  if (!filter[x & MASK]) {
    return false;
  }
  int key = x % hmod;
  for (lista p = h[key]; p; p = p->next) {
    if (p->val == x) {
      return p->cnt > 0;
    }
  }
  return false;
}

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

void modifyPaths(int u, int par, int depth, bool t) {
  if (t) {
    add(h1[u]);
  } else {
    rem(h1[u]);
  }
  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 (ok(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) {
    dfs1(c, 0, 0);
    for (int v : g[c]) {
      if (!vis[v]) {
        modifyPaths(v, c, 2, false);
        nodes.clear();
        nodes.emplace_back(0);
        nodes.emplace_back(c);
        if (dfs2(v, c, 2, len)) {
          modifyPaths(v, c, 2, true);
          modifyPaths(c, 0, 1, false);
          return true;
        }
        modifyPaths(v, c, 2, true);
      }
    }
    modifyPaths(c, 0, 1, false);
    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 3 ms 2124 KB Output is correct
2 Correct 8 ms 3276 KB Output is correct
3 Correct 32 ms 13516 KB Output is correct
4 Correct 41 ms 11084 KB Output is correct
5 Correct 2 ms 1612 KB Output is correct
6 Correct 1 ms 1612 KB Output is correct
7 Correct 1 ms 1612 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4216 ms 55916 KB Output is correct
2 Correct 3154 ms 55864 KB Output is correct
3 Correct 1874 ms 52476 KB Output is correct
4 Correct 2231 ms 53404 KB Output is correct
5 Correct 4849 ms 60400 KB Output is correct
6 Correct 382 ms 42372 KB Output is correct

Subtask #3
0 / 31.0

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

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2124 KB Output is correct
2 Correct 8 ms 3276 KB Output is correct
3 Correct 32 ms 13516 KB Output is correct
4 Correct 41 ms 11084 KB Output is correct
5 Correct 2 ms 1612 KB Output is correct
6 Correct 1 ms 1612 KB Output is correct
7 Correct 1 ms 1612 KB Output is correct
8 Correct 4216 ms 55916 KB Output is correct
9 Correct 3154 ms 55864 KB Output is correct
10 Correct 1874 ms 52476 KB Output is correct
11 Correct 2231 ms 53404 KB Output is correct
12 Correct 4849 ms 60400 KB Output is correct
13 Correct 382 ms 42372 KB Output is correct
14 Execution timed out 5056 ms 55060 KB Time limit exceeded
15 Halted 0 ms 0 KB -