oj.uz

Submission #198564

# Submission time Handle Problem Language Result Execution time Memory
198564 2020-01-26T15:46:57 Z quocnguyen1012 Lampice (COCI19_lampice) C++14
0 / 110
 5000 ms 12744 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, mod = 1e9 + 7;

vector<int> adj[maxn];
int par[maxn][17], sz[maxn];
int N; string str;
int depth[maxn];
int POW[maxn];
ll HashUp[maxn], HashDown[maxn];
bool vis[maxn], ret;
vector<int> node;
int tin[maxn], tout[maxn], nTime;
vector<pair<int, 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) % mod;
    HashUp[v] = (HashUp[u] + POW[depth[v] - 1] * (str[v] - 'a' + 1)) % mod;
    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];
}

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

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;
    int 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;
      ///cerr << A << ' ' << B << '\n';
      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)
{
  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 % mod;
  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
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2045 ms 12744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

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

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -