oj.uz

Submission #1088780

# Submission time Handle Problem Language Result Execution time Memory
1088780 2024-09-15T04:02:43 Z fryingduc Lampice (COCI19_lampice) C++17
110 / 110
 1772 ms 16856 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(!prev)
      save.clear();

    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
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8024 KB Output is correct
2 Correct 8 ms 8188 KB Output is correct
3 Correct 19 ms 8156 KB Output is correct
4 Correct 19 ms 8028 KB Output is correct
5 Correct 3 ms 7772 KB Output is correct
6 Correct 4 ms 7772 KB Output is correct
7 Correct 4 ms 7772 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 717 ms 15584 KB Output is correct
2 Correct 729 ms 15828 KB Output is correct
3 Correct 470 ms 16088 KB Output is correct
4 Correct 609 ms 16340 KB Output is correct
5 Correct 955 ms 16856 KB Output is correct
6 Correct 77 ms 15720 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1393 ms 13964 KB Output is correct
2 Correct 1772 ms 13524 KB Output is correct
3 Correct 1515 ms 13976 KB Output is correct
4 Correct 1324 ms 13076 KB Output is correct
5 Correct 1125 ms 13020 KB Output is correct
6 Correct 1085 ms 12740 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8024 KB Output is correct
2 Correct 8 ms 8188 KB Output is correct
3 Correct 19 ms 8156 KB Output is correct
4 Correct 19 ms 8028 KB Output is correct
5 Correct 3 ms 7772 KB Output is correct
6 Correct 4 ms 7772 KB Output is correct
7 Correct 4 ms 7772 KB Output is correct
8 Correct 717 ms 15584 KB Output is correct
9 Correct 729 ms 15828 KB Output is correct
10 Correct 470 ms 16088 KB Output is correct
11 Correct 609 ms 16340 KB Output is correct
12 Correct 955 ms 16856 KB Output is correct
13 Correct 77 ms 15720 KB Output is correct
14 Correct 1393 ms 13964 KB Output is correct
15 Correct 1772 ms 13524 KB Output is correct
16 Correct 1515 ms 13976 KB Output is correct
17 Correct 1324 ms 13076 KB Output is correct
18 Correct 1125 ms 13020 KB Output is correct
19 Correct 1085 ms 12740 KB Output is correct
20 Correct 1024 ms 11296 KB Output is correct
21 Correct 1320 ms 11988 KB Output is correct
22 Correct 1604 ms 12396 KB Output is correct
23 Correct 444 ms 10584 KB Output is correct
24 Correct 1078 ms 11992 KB Output is correct
25 Correct 1010 ms 11488 KB Output is correct
26 Correct 1376 ms 13528 KB Output is correct
27 Correct 1672 ms 12776 KB Output is correct
28 Correct 784 ms 10812 KB Output is correct
29 Correct 843 ms 10840 KB Output is correct
30 Correct 974 ms 12596 KB Output is correct
31 Correct 826 ms 11472 KB Output is correct
32 Correct 926 ms 13520 KB Output is correct
33 Correct 1010 ms 12460 KB Output is correct