oj.uz

Submission #638226

# Submission time Handle Problem Language Result Execution time Memory
638226 2022-09-05T02:38:58 Z iee Lampice (COCI19_lampice) C++17
42 / 110
 273 ms 49132 KB 
// iee
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <set>
#include <map>

#define rep(i, a, b) for (auto i = (a); i <= (b); ++i)
#define per(i, a, b) for (auto i = (a); i >= (b); --i)
#define fi first
#define se second
using ll = long long;
using ull = unsigned long long;
using namespace std;
void work(int);

template <class T> void read(T &x) {
  x = 0; int f = 1, ch = getchar();
  while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
  while (isdigit(ch)) x = x * 10 + (ch - '0'), ch = getchar();
  x *= f;
}

int main() {
  int TT = 1; // cin >> TT;
  rep(CAS, 1, TT)
    work(CAS);
  return 0;
}
const int N = 5e4 + 5;
int n, u[N], v[N];
char a[N];
namespace bf {
const int N = 3005, base = 31;
vector<int> e[N];
ull hpath[N][N];
void dfs1(const int &rt, int u, int pr, ull h) {
  h = h * base + (a[u] - 'a' + 1);
  hpath[rt][u] = h;
  for (int v: e[u]) if (v != pr)
    dfs1(rt, v, u, h);
}
int ans, st[N], top;
void dfs2(const int &rt, int u, int pr) {
  st[++top] = u;
  if (top % 2 == 0 && hpath[rt][st[top / 2]] == hpath[u][st[top / 2 + 1]] || top % 2 == 1 && hpath[rt][st[top / 2 + 1]] == hpath[u][st[top / 2 + 1]]) ans = max(ans, top);
  for (int v: e[u]) if (v != pr)
    dfs2(rt, v, u);
  --top;
}
void work() {
  rep(i, 1, n - 1) e[::u[i]].push_back(::v[i]), e[::v[i]].push_back(::u[i]);
  rep(i, 1, n) dfs1(i, i, -1, 0ull);
  rep(i, 1, n) top = 0, dfs2(i, i, 0);
  cout << ans;
}

}

namespace lian {
vector<int> e[N];
const int base = 31;
char s[N];
int tot;
void dfs(int u, int pr) {
  s[++tot] = a[u];
  for (int v: e[u]) if (v != pr)
    dfs(v, u);
}
ull h[N], hr[N], pw[N];
ull qh(int l, int r) { return h[r] - h[l - 1] * pw[r - l + 1]; }
ull qhr(int l, int r) { return hr[l] - hr[r + 1] * pw[r - l + 1]; }
void work() {
  rep(i, 1, n - 1) e[::u[i]].push_back(v[i]), e[::v[i]].push_back(::u[i]);
  rep(i, 1, n) if (e[i].size() == 1) { dfs(i, 0); break; }
  rep(i, 1, n) h[i] = h[i - 1] * base + (s[i] - 'a' + 1);
  per(i, n, 1) hr[i] = hr[i + 1] * base + (s[i] - 'a' + 1);
  pw[0] = 1;
  rep(i, 1, n) pw[i] = pw[i - 1] * base;
  int ans = 0;
  rep(i, 1, n) {
      int l = 1, r = min(i, n - i + 1);
      while (l < r) {
        int mid = l + r + 1 >> 1;
        if (qh(i - mid + 1, i) == qhr(i + 1, i + mid)) l = mid;
        else r = mid - 1;
      }
      ans = max(ans, l * 2);
      l = 1, r = min(i, n - i + 1);
      while (l < r) {
        int mid = l + r + 1 >> 1;
        if (qh(i - mid + 1, i) == qhr(i, i + mid - 1)) l = mid;
        else r = mid - 1;
      }
      ans = max(ans, l * 2 - 1);
  }
  cout << ans;
}
}

void work(int CASE) {
  scanf("%d%s", &n, a + 1);
  rep(i, 1, n - 1) scanf("%d%d", u + i, v + i);
  if (n <= 3000) { bf::work(); return; }
  lian::work();
}

Compilation message

lampice.cpp: In function 'void bf::dfs2(const int&, int, int)':
lampice.cpp:48:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   48 |   if (top % 2 == 0 && hpath[rt][st[top / 2]] == hpath[u][st[top / 2 + 1]] || top % 2 == 1 && hpath[rt][st[top / 2 + 1]] == hpath[u][st[top / 2 + 1]]) ans = max(ans, top);
      |       ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp: In function 'void lian::work()':
lampice.cpp:86:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |         int mid = l + r + 1 >> 1;
      |                   ~~~~~~^~~
lampice.cpp:93:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |         int mid = l + r + 1 >> 1;
      |                   ~~~~~~^~~
lampice.cpp: In function 'void work(int)':
lampice.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   scanf("%d%s", &n, a + 1);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
lampice.cpp:105:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |   rep(i, 1, n - 1) scanf("%d%d", u + i, v + i);
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3924 KB Output is correct
2 Correct 22 ms 9368 KB Output is correct
3 Correct 120 ms 25420 KB Output is correct
4 Correct 273 ms 49132 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6372 KB Output is correct
2 Correct 16 ms 6996 KB Output is correct
3 Correct 17 ms 7204 KB Output is correct
4 Correct 18 ms 7452 KB Output is correct
5 Correct 19 ms 7628 KB Output is correct
6 Correct 18 ms 7628 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5448 KB Output is correct
2 Incorrect 23 ms 5636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3924 KB Output is correct
2 Correct 22 ms 9368 KB Output is correct
3 Correct 120 ms 25420 KB Output is correct
4 Correct 273 ms 49132 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 17 ms 6372 KB Output is correct
9 Correct 16 ms 6996 KB Output is correct
10 Correct 17 ms 7204 KB Output is correct
11 Correct 18 ms 7452 KB Output is correct
12 Correct 19 ms 7628 KB Output is correct
13 Correct 18 ms 7628 KB Output is correct
14 Correct 21 ms 5448 KB Output is correct
15 Incorrect 23 ms 5636 KB Output isn't correct
16 Halted 0 ms 0 KB -