oj.uz

Submission #197988

# Submission time Handle Problem Language Result Execution time Memory
197988 2020-01-24T12:41:30 Z model_code Lampice (COCI19_lampice) C++17
73 / 110
 5000 ms 6008 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50010;

int n;
char input[MAXN];
vector<int> adj[MAXN];

int stk_sz = 1;
char stk[2 * MAXN];
int pivot = 0;
int ans = 1;

int manacher() {
  static int rad[2 * MAXN];

  int x = 0;
  for (int i = 1; i < stk_sz; ++i) {
    int &r = rad[i] = 0;
    if (i <= x + rad[x])
      r = min(rad[2 * x - i], x + rad[x] - i);
    while (i - r - 1 >= 0 && i + r + 1 < stk_sz &&
        stk[i - r - 1] == stk[i + r + 1]) ++r;
    if (i + r >= x + rad[x]) x = i;
  }

  int ret = 0;
  for (int i = 0; i < stk_sz; ++i)
    if (rad[i] > ret)
      ret = rad[i];
  return ret;
}

void dfs(int x, int prev = -1) {
  stk[stk_sz++] = input[x];
  stk[stk_sz++] = '*';
  if (adj[x].size() == 1 && x < pivot)
    ans = max(ans, manacher());
  for (int y : adj[x]) {
    if (y == prev) continue;
    dfs(y, x);
  }
  stk_sz -= 2;
}

int main(void) {
  ios_base::sync_with_stdio(false);
  cin >> n;
  cin >> input;
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    u--; v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  stk[0] = '*';
  for (int i = 0; i < n; ++i) {
    if (adj[i].size() != 1)
      continue;
    pivot = i;
    dfs(i);
  }
  cout << ans << endl;
  return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1528 KB Output is correct
2 Correct 27 ms 1528 KB Output is correct
3 Correct 174 ms 1652 KB Output is correct
4 Correct 580 ms 1640 KB Output is correct
5 Correct 3 ms 1528 KB Output is correct
6 Correct 3 ms 1528 KB Output is correct
7 Correct 3 ms 1528 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5368 KB Output is correct
2 Correct 26 ms 5496 KB Output is correct
3 Correct 23 ms 5496 KB Output is correct
4 Correct 25 ms 5756 KB Output is correct
5 Correct 26 ms 5908 KB Output is correct
6 Correct 25 ms 6008 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 929 ms 4168 KB Output is correct
2 Correct 748 ms 3836 KB Output is correct
3 Correct 1463 ms 4200 KB Output is correct
4 Correct 966 ms 4324 KB Output is correct
5 Correct 592 ms 3636 KB Output is correct
6 Correct 638 ms 3556 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1528 KB Output is correct
2 Correct 27 ms 1528 KB Output is correct
3 Correct 174 ms 1652 KB Output is correct
4 Correct 580 ms 1640 KB Output is correct
5 Correct 3 ms 1528 KB Output is correct
6 Correct 3 ms 1528 KB Output is correct
7 Correct 3 ms 1528 KB Output is correct
8 Correct 26 ms 5368 KB Output is correct
9 Correct 26 ms 5496 KB Output is correct
10 Correct 23 ms 5496 KB Output is correct
11 Correct 25 ms 5756 KB Output is correct
12 Correct 26 ms 5908 KB Output is correct
13 Correct 25 ms 6008 KB Output is correct
14 Correct 929 ms 4168 KB Output is correct
15 Correct 748 ms 3836 KB Output is correct
16 Correct 1463 ms 4200 KB Output is correct
17 Correct 966 ms 4324 KB Output is correct
18 Correct 592 ms 3636 KB Output is correct
19 Correct 638 ms 3556 KB Output is correct
20 Execution timed out 5052 ms 3064 KB Time limit exceeded
21 Halted 0 ms 0 KB -