Submission #848932

#	Time	Username	Problem	Language	Result	Execution time	Memory
848932		qthang2k11	Lampice (COCI19_lampice)	C++17	110 / 110	2439 ms	11700 KiB

lampice

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 5e4 + 5, mod = 1e9 + 7, base = 31;
unordered_set<int> mp, existed;
int xuoi[N], nguoc[N], pw[N];
int dpt[N], up[N], sz[N];
bool rem[N], checked;
vector <int> adj[N];
int ans = 1, n, r;
char a[N];

int add(int value, char x) {
   return (value * base + x - 'a' + 1);
}

int dfs(int x, int p) {
   sz[x] = 1;
   for (int y: adj[x]) {
      if (y == p || rem[y]) continue;
      sz[x] += dfs(y, x);
   }

   return sz[x];
}

void down(int x, int p, int len) {
   dpt[x] = dpt[p] + 1;
   up[dpt[x]] = x;
   if (dpt[x] >= len || checked) return;
   int curlen = dpt[x] + 1;
   if (curlen == len) {
      ///centroid->con
      ///xuoi == nguoc
      int Xuoi = xuoi[x] + (a[r] - 'a' + 1) * pw[dpt[x]];
      int Nguoc = nguoc[x] * base + (a[r] - 'a' + 1);
      if (Xuoi == Nguoc) return checked = 1, void();
   }
   mp.insert(xuoi[x]);
   for (int y: adj[x]) {
      if (y == p || rem[y]) continue;
      xuoi[y] = add(xuoi[x], a[y]);
      nguoc[y] = nguoc[x] + (a[y] - 'a' + 1) * pw[dpt[x]];
      down(y, x, len);
   }
   if (checked) return;
   if (curlen >= (len + 1) / 2) {
      int xx = len - curlen;
      if (xx <= curlen) {
         ///curstr[curlen-1,...,curlen-x]..curstr
         if (xx > dpt[x]) return;
         int chaxet = up[dpt[x] - xx]; //jump(x,xx);///log
         int Xuoi = xuoi[chaxet] + (a[r] - 'a' + 1) * pw[dpt[chaxet]];
         int Nguoc = nguoc[chaxet] * base + (a[r] - 'a' + 1);
         if (Xuoi != Nguoc) return;
         int suffix = xuoi[x] - xuoi[chaxet] * pw[xx];
         if (existed.find(suffix) != existed.end())
            return checked = 1, void();
      }
   }
}

bool ok(int x, int len) {
   if (sz[x] < len) return 0;
   if (len <= 1) return 1;
   dpt[x] = 0;
   xuoi[x] = nguoc[x] = 0;
   r = x;
   existed.clear();
   checked = 0;
   for (int y: adj[x]) {
      if (rem[y]) continue;
      mp.clear();
      xuoi[y] = nguoc[y] = a[y] - 'a' + 1;
      down(y, x, len);
      for (int x: mp)
         existed.insert(x);
   }
   return checked;
}

void sus(int x, int p) {
   sz[x] = 1;
   for (int y: adj[x]) {
      if (y == p || rem[y]) continue;
      sus(y, x);
      sz[x] += sz[y];
   }
}

void solve(int x) {
   {
      ///chan
      int l = ans / 2, r = sz[x];
      while (l <= r) {
         int mid = (l + r) / 2;
         if (ok(x, mid * 2)) {
            ans = max(ans, mid * 2);
            l = mid + 1;
         } else r = mid - 1;
      }
   }
   {
      ///le
      int l = ans / 2, r = sz[x];
      while (l <= r) {
         int mid = (l + r) / 2;
         if (ok(x, mid * 2 + 1)) {
            ans = max(ans, mid * 2 + 1);
            l = mid + 1;
         } else r = mid - 1;
      }
   }
   reverse(adj[x].begin(), adj[x].end());
}

int find_centroid(int x, int p, int tot) {
   for (int y: adj[x])
      if (y != p && !rem[y] && sz[y] > tot / 2)
         return find_centroid(y, x, tot);
   return x;
}

void build(int x = 1) {
   int c = find_centroid(x, 0, dfs(x, 0));
   rem[c] = 1;
   sus(c, 0);
   solve(c);
   solve(c);
   for (int y: adj[c])
      if (!rem[y])
         build(y);
}

int32_t main() {
   cin.tie(0)->sync_with_stdio(0);
   cin >> n;
   pw[0] = 1;
   for (int i = 1; i <= n; i++) pw[i] = 1ll * pw[i - 1] * base;
   for (int i = 1; i <= n; i++) cin >> a[i];
   for (int i = 1; i < n; i++) {
      int x, y;
      cin >> x >> y;
      adj[x].push_back(y);
      adj[y].push_back(x);
   }
   build();
   cout << ans;
   return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 31 / 31
• Subtask 4: 37 / 37