oj.uz

Submission #1088779

# Submission time Handle Problem Language Result Execution time Memory
1088779 2024-09-15T04:00:39 Z fryingduc Lampice (COCI19_lampice) C++17
0 / 110
 5000 ms 18784 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else 
#define debug(...)     
#endif

const int maxn = 1e5 + 5;
const int base = 31;
const int mod = 1e9 + 9;
int p[maxn];
vector<int> g[maxn];
int n, a[maxn];
string s;
bool del[maxn];
int sz[maxn];

vector<pair<int, int>> save;
map<int, bool> mp[maxn];

int path_len, max_dep;

bool exist;

int find_centroid(int u, int prev, int n) {
  for(auto v:g[u]) {
    if(!del[v] and v != prev and sz[v] * 2 > n) 
      return find_centroid(v, u, n);
  }
  return u;
}
void re_dfs(int u, int prev) {
  sz[u] = 1;
  for(auto v:g[u]) {
    if(v == prev || del[v]) continue;
    re_dfs(v, u);
    sz[u] += sz[v];
  }
}

bool dfs_get(int u, int prev, int dep, int hu, int hd) {
  if(dep > path_len)
    return 0;

  if(prev) 
    hd = (1ll * hd * base + (s[u] - 'a' + 1)) % mod;
  hu = (hu + 1ll * p[dep - 1] * (s[u] - 'a' + 1) % mod) % mod;

  int x = (1ll * hu * p[path_len - dep] % mod - hd + mod) % mod;

  if(!prev) 
    mp[dep][x] = 1;

  if(mp[path_len - dep + 1].count(x)) {
    return 1;
  }

  for(auto v:g[u]) {
    if(del[v] || v == prev) continue;

    if(dfs_get(v, u, dep + 1, hu, hd)) 
      return 1;

    if(!prev) {
      for(auto i:save) {
        mp[i.first][i.second] = 1;
      }
    }
  }
  max_dep = max(dep, max_dep);
  save.push_back({dep, x});

  return 0;
}
void decompose(int u, int prev) {
  if(exist)
    return;
  re_dfs(u, prev);

  int c = find_centroid(u, prev, sz[u]);

  exist |= dfs_get(c, 0, 1, 0, 0);
  for(int i = 1; i <= max_dep; ++i) {
    mp[i].clear();
  }
  max_dep = 0;
  del[c] = 1;

  for(auto v:g[c]) {
    if(del[v] || v == prev) continue;
    decompose(v, c);
  }
}
bool check(int mid) {
  path_len = mid;
  memset(del, 0, sizeof(del));
  exist = 0;
  decompose(1, 0);
  // debug(mid, exist);
  return exist;
}
void solve() {
  cin >> n >> s;
  s = ' ' + s;
  for(int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  int res = 1;
  int l = 1, r = (n - 1) / 2;
  while(l <= r) {
    int mid = (l + r) >> 1;
    if(check(mid * 2 + 1)) {
      res = max(res, mid * 2 + 1);
      l = mid + 1;
    }
    else {
      r = mid - 1;
    }
  }
  l = 1, r = n / 2;
  while(l <= r) {
    int mid = (l + r) / 2;
    if(check(mid * 2)) {
      res = max(res, mid * 2);
      l = mid + 1;
    }
    else {
      r = mid - 1;
    }
  }
  cout << res;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  p[0] = 1;
  for(int i = 1; i < maxn; ++i) {
    p[i] = 1ll * p[i - 1] * base % mod;
  }

  solve();

  return 0;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 778 ms 8276 KB Output is correct
2 Execution timed out 5025 ms 8864 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5064 ms 18784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5069 ms 16400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 778 ms 8276 KB Output is correct
2 Execution timed out 5025 ms 8864 KB Time limit exceeded
3 Halted 0 ms 0 KB -