oj.uz

Submission #198568

# Submission time Handle Problem Language Result Execution time Memory
198568 2020-01-26T16:05:59 Z quocnguyen1012 Lampice (COCI19_lampice) C++14
110 / 110
 4969 ms 14836 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 5e4 + 5, base = 131;

vector<int> adj[maxn];
int par[maxn][17], sz[maxn];
int N; string str;
int depth[maxn];
ll POW[maxn];
ll HashUp[maxn], HashDown[maxn];
bool vis[maxn], ret;
vector<int> node;
int tin[maxn], tout[maxn], nTime;
vector<pair<ll, int>> same[maxn];

void findsz(int u, int p)
{
  sz[u] = 1;
  for (int v : adj[u]){
    if (v == p || vis[v] == true) continue;
    findsz(v, u);
    sz[u] += sz[v];
  }
}

void prepare(int u, int p)
{
  node.pb(u);
  tin[u] = ++nTime;
  same[depth[u]].pb(mp(HashDown[u], u));
  for (int i = 1; (1 << i) <= N; ++i)
    par[u][i] = par[par[u][i - 1]][i - 1];
  for (int v : adj[u]){
    if (v == p || vis[v] == true) continue;
    par[v][0] = u;
    depth[v] = depth[u] + 1;
    HashDown[v] = HashDown[u] * base + str[v] - 'a' + 1;
    HashUp[v] = HashUp[u] + POW[depth[v] - 1] * (str[v] - 'a' + 1);
    prepare(v, u);
  }
  tout[u] = nTime;
}

bool inside(int u, int v)
{
  return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int findcen(int u, int p, int need)
{
  for (int v : adj[u]){
    if (v == p || vis[v] == true) continue;
    if (sz[v] > need / 2) return findcen(v, u, need);
  }
  return u;
}

int lift(int x, int y)
{
  for (int k = 16; k >= 0; --k){
    if (y >> k & 1) x = par[x][k];
  }
  return x;
}

int LCA(int x, int y)
{
  if (depth[x] < depth[y]) swap(x, y);
  if (inside(y, x)) return y;
  for (int k = 16; k >= 0; --k){
    if (depth[par[x][k]] >= depth[y]){
      x = par[x][k];
    }
  }
  if (x == y) return x;
  for (int k = 16; k >= 0; --k){
    if (par[x][k] != par[y][k]){
      x = par[x][k];
      y = par[y][k];
    }
  }
  return par[x][0];
}

ll GetHash(int u, int v)
{
  return HashDown[u] - HashDown[par[v][0]] * POW[depth[u] - depth[v] + 1];
}

void solve(int u, int len)
{
  if (ret) return;
  HashDown[u] = str[u] - 'a' + 1;
  HashUp[u] = str[u] - 'a' + 1;
  node.clear();
  par[u][0] = 0; depth[u] = 1; nTime = 0;
  prepare(u, u);
  for (int i = 1; i <= N; ++i){
    if (same[i].empty()) break;
    sort(same[i].begin(), same[i].end());
  }
  for (int A : node){
    if (ret) break;
    int dneed = len - depth[A] + 1;
    if (dneed > depth[A] || dneed < 1) continue;
    int C = lift(A, dneed - 1);
    if (HashDown[C] != HashUp[C]) continue;
    ll hneed = GetHash(A, C);
    int l = lower_bound(same[dneed].begin(), same[dneed].end(), mp(hneed, -1)) - same[dneed].begin();
    if (l == (int)same[dneed].size() || same[dneed][l].fi != hneed) continue;
    while (l < (int)same[dneed].size()){
      if (same[dneed][l].fi != hneed) break;
      int B = same[dneed][l].se;
      if (LCA(A, B) == u){
        ret = true;
        break;
      }
      else ++l;
    }
  }
  for (int i = 1; i <= N; ++i){
    if (same[i].empty()) break;
    same[i].clear();
  }
}

void centroid(int root, int len)
{
  if (ret) return;
  findsz(root, root);
  int u = findcen(root, root, sz[root]);
  vis[u] = true;
  solve(u, len);
  for (int v : adj[u]){
    if (vis[v] == false){
      centroid(v, len);
    }
  }
}

bool check(int len, int ok)
{
  len = len * 2 + ok;
  ret = false;
  for (int i = 1; i <= N; ++i) vis[i] = false;
  centroid(1, len);
  return ret;
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N >> str; str = " " + str;
  for (int i = 1; i < N; ++i){
    int u, v; cin >> u >> v;
    adj[u].pb(v); adj[v].pb(u);
  }
  POW[0] = 1;
  for (int i = 1; i <= N; ++i)
    POW[i] = 1ll * POW[i - 1] * base;
  int l = 0, r = N / 2, mid;
  while (l <= r){
    mid = (l + r) / 2;
    if (check(mid, 1)) l = mid + 1;
    else r = mid - 1;
  }
  int res = (r * 2 + 1);
  l = 1, r = N / 2, mid;
  while (l <= r){
    mid = (l + r) / 2;
    if (check(mid, 0)) l = mid + 1;
    else r = mid - 1;
  }
  res = max(res, r * 2);
  cout << res << '\n';
}

Compilation message

lampice.cpp: In function 'int main()':
lampice.cpp:180:24: warning: right operand of comma operator has no effect [-Wunused-value]
   l = 1, r = N / 2, mid;
                        ^
lampice.cpp:162:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
lampice.cpp:163:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2808 KB Output is correct
2 Correct 13 ms 2808 KB Output is correct
3 Correct 29 ms 2936 KB Output is correct
4 Correct 41 ms 3192 KB Output is correct
5 Correct 7 ms 2808 KB Output is correct
6 Correct 7 ms 2680 KB Output is correct
7 Correct 7 ms 2680 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1852 ms 12792 KB Output is correct
2 Correct 1273 ms 13556 KB Output is correct
3 Correct 762 ms 13808 KB Output is correct
4 Correct 1020 ms 14324 KB Output is correct
5 Correct 1720 ms 14836 KB Output is correct
6 Correct 322 ms 14836 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4793 ms 12024 KB Output is correct
2 Correct 4623 ms 12164 KB Output is correct
3 Correct 4351 ms 12404 KB Output is correct
4 Correct 4969 ms 12604 KB Output is correct
5 Correct 3006 ms 11248 KB Output is correct
6 Correct 3053 ms 10652 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2808 KB Output is correct
2 Correct 13 ms 2808 KB Output is correct
3 Correct 29 ms 2936 KB Output is correct
4 Correct 41 ms 3192 KB Output is correct
5 Correct 7 ms 2808 KB Output is correct
6 Correct 7 ms 2680 KB Output is correct
7 Correct 7 ms 2680 KB Output is correct
8 Correct 1852 ms 12792 KB Output is correct
9 Correct 1273 ms 13556 KB Output is correct
10 Correct 762 ms 13808 KB Output is correct
11 Correct 1020 ms 14324 KB Output is correct
12 Correct 1720 ms 14836 KB Output is correct
13 Correct 322 ms 14836 KB Output is correct
14 Correct 4793 ms 12024 KB Output is correct
15 Correct 4623 ms 12164 KB Output is correct
16 Correct 4351 ms 12404 KB Output is correct
17 Correct 4969 ms 12604 KB Output is correct
18 Correct 3006 ms 11248 KB Output is correct
19 Correct 3053 ms 10652 KB Output is correct
20 Correct 2406 ms 11128 KB Output is correct
21 Correct 2399 ms 10996 KB Output is correct
22 Correct 3360 ms 11308 KB Output is correct
23 Correct 2209 ms 11248 KB Output is correct
24 Correct 3539 ms 12148 KB Output is correct
25 Correct 3578 ms 12272 KB Output is correct
26 Correct 3899 ms 12760 KB Output is correct
27 Correct 4505 ms 12152 KB Output is correct
28 Correct 3367 ms 11892 KB Output is correct
29 Correct 3834 ms 12200 KB Output is correct
30 Correct 3642 ms 12916 KB Output is correct
31 Correct 3590 ms 12020 KB Output is correct
32 Correct 2713 ms 13532 KB Output is correct
33 Correct 1854 ms 11632 KB Output is correct