Submission #530813

#	Time	Username	Problem	Language	Result	Execution time	Memory
530813		cadmiumsky	Lampice (COCI19_lampice)	C++14	0 / 110	5095 ms	10972 KiB

lampice

#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int nmax = 5e4 + 5;

#define int ll
#define hash isdoaohhdkgf
const int mod = 1e9 + 9;  
int p[nmax][2];
struct hash {
  int v[2], len;
  hash() {
    v[0] = v[1] = len = 0;
  }
  hash(char ch) {
    ch -= 'a' - 1;
    v[0] = ch, v[1] = ch, len = 1;
  }
  hash(int a, int b, int c) {
    v[0] = a, v[1] = b, len = c;
  }
  hash operator + (const hash& x) const {
    return hash((v[0] * p[x.len][0] + x.v[0]) % mod,
                (v[1] * p[x.len][1] + x.v[1]) % mod,
                len + x.len);
  }
  void operator +=(const hash& x)  {*this = *this + x;}
  void operator +=(const char& x)  {*this = *this + hash(x);}
  bool operator == (const hash& x) {return v[0] == x.v[0] && v[1] == x.v[1] && len == x.len;}
  hash operator -(const hash& x) const {
    return hash(((v[0] - x.v[0] * p[len - x.len][0] % mod + mod) % mod),
                ((v[1] - x.v[1] * p[len - x.len][1] % mod + mod) % mod),
                len - x.len);
  }
  
  ll operator()() const {
    return v[0] * mod + v[1];
  }
};
char ch[nmax];
int n;
vector<int> g[nmax];

#undef int

namespace READ {
  void init() {
    p[0][0] = 1;
    p[0][1] = 1;
    p[1][1] = 37;
    p[1][0] = 666013;
    for(int i = 2; i < nmax; i++)
      p[i][0] = (p[i - 1][0] * p[1][0]) % mod, p[i][1] = (p[i - 1][1] * p[1][1]) % mod;
  }
  void read() {
    cin >> n;
    for(int i = 1; i <= n; i++)
      cin >> ch[i];
    for(int i = 1, x, y; i < n; i++) {
      cin >> x >> y;
      g[x].push_back(y);
      g[y].push_back(x);
    }
  }
}
namespace CENTROID {
  bool merge = 0;
  int lim = 0;
  int area[nmax];
  int iscentr[nmax];
  unordered_multiset<ll> ms;
  int depth[nmax];
  int ispal[nmax];
  int mkarea(int node, int f) {
    ispal[node] = 0;
    if(iscentr[node])
      return 0;
    area[node] = 1;
    for(auto x : g[node]) {
      if(x == f)
        continue;
      area[node] += mkarea(x, node);
    }
    return area[node];
  } 
  int getcentroid(int node, int f, int limit) {
    for(auto x : g[node]) {
      if(iscentr[x] || x == f)
        continue;
      if(area[x] >= limit / 2)
        return getcentroid(x, node, limit);
    }
    return node;
  }
  void upd(int node, int f, bool aggr, hash h = hash()) {
    depth[node] = depth[f] + 1;
    h += ch[node];
    if(aggr)
      ms.insert(h());
    else
      ms.erase(h());
    for(auto x : g[node]) {
      if(x == f || iscentr[x])
        continue;
      upd(x, node, aggr, h);
    }
    return;
  }
  int st[nmax], ptr = 0;
  hash mst[nmax];
  void oper(int node, int f, hash fr = hash(), hash bk = hash()) {
    fr = fr + hash(ch[node]);
    bk = hash(ch[node]) + bk;
    mst[ptr] = fr;
    st[ptr++] = node;
    if(ptr <= lim) {
      if(fr == bk)
        ispal[node] = 1;
      if(ptr == lim && ispal[node])
        merge = 1;
      else {
        int k = 2 * ptr - 1 - lim;
        if(k >= 0) {
          if(ms.count((fr - mst[k])()) && ispal[st[k]])
            merge = 1;
        } 
      }
      for(auto x : g[node]) {
        if(x == f || iscentr[x])
          continue;
        oper(x, node, fr, bk);
      }
    }
    ptr--;
  }
  void mkcentroid(int node) {
    mkarea(node, node);
    int root = getcentroid(node, node, area[node]);
    iscentr[root] = 1;
    node = root;
    ispal[root] = 1;
    for(auto x : g[root])
      upd(x, node, 1);
    ptr = 0;
    depth[node] = 0;
    mst[ptr] = hash(ch[root]);
    st[ptr++] = root;
    for(auto x : g[root]) {
      if(iscentr[x])
        continue;
      upd(x, node, 0);
      oper(x, node, hash(ch[root]), hash(ch[root]));
      upd(x, node, 1);
    }
    ms.erase(ms.begin(), ms.end());
    for(auto x : g[root]) {
      if(!iscentr[x])
        mkcentroid(x);
    }
    ms.erase(ms.begin(), ms.end());
  }
  bool query(int len) {
    ms.erase(ms.begin(), ms.end());
    fill(iscentr, iscentr + n + 1, 0);
    lim = len;
    merge = 0;
    mkcentroid(1);
    //cout << "----------------------\n";
    return merge;
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  READ::init();
  READ::read();
  int temp, imp = 1, ev = 0;
  for(int i = 18; i > 0; i--) {
    if(CENTROID::query(imp + (1 << i)))
      imp += (1 << i);
  }
  for(int i = 18; i > 0; i--) {
    if(CENTROID::query(ev + (1 << i)))
      ev += (1 << i);
  }
  cout << max(imp, ev) << '\n';
}

Compilation message (stderr)

lampice.cpp: In function 'int main()':
lampice.cpp:179:7: warning: unused variable 'temp' [-Wunused-variable]
  179 |   int temp, imp = 1, ev = 0;
      |       ^~~~

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