제출 #638226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
638226		iee	Lampice (COCI19_lampice)	C++17	42 / 110	273 ms	49132 KiB

lampice

// 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();
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 17
• Subtask 2: 25 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37