oj.uz

Submission #226611

# Submission time Handle Problem Language Result Execution time Memory
226611 2020-04-24T14:09:31 Z quocnguyen1012 Rima (COCI17_rima) C++14
140 / 140
 577 ms 42232 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 5e5 + 5, mod = 1e9 + 7, base = 31;

int par[maxn], sz[maxn];
int N;
vector<int> adj[maxn];
ll ha[maxn], pha[maxn];
bool vis[maxn];
bool hpar[maxn];

int finds(int u)
{
  if(par[u] == u) return u;
  return par[u] = finds(par[u]);
}

void merges(int u, int v)
{
  u = par[u]; v = par[v];
  if(u == v) return;
  if(sz[v] > sz[u]) swap(u, v);
  sz[u] += sz[v]; par[v] = u;
}

ll gethash(string s)
{
  ll Hash = 0;
  for(int i = 0; i < (int)s.size(); ++i){
    Hash = (Hash * base + s[i] - 'a' + 1) % mod;
  }
  return Hash;
}

ii dfs(int u, int p = -1)
{
  int w = sz[u] > 1 and p != -1;
  ii ret = mp(sz[u] + w, sz[u]);
  for(int v : adj[u]) if(v != p){
    auto tmp = dfs(v, u);
    ret.fi = max(ret.fi, tmp.fi);
    ret.fi = max(ret.fi, tmp.se + ret.se + w);
    ret.se = max(ret.se, sz[u] + tmp.se);
  }
  return ret;
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  cin >> N;
  iota(par + 1, par + 1 + N, 1);
  fill(sz + 1, sz + 1 + N, 1);
  for(int i = 1; i <= N; ++i){
    string str; cin >> str;
    reverse(str.begin(), str.end());
    ha[i] = gethash(str); str.pop_back();
    pha[i] = gethash(str);
  }
  map<ll, int> ma;
  for(int i = 1; i <= N; ++i){
    if(!ma.count(pha[i])){
      ma[pha[i]] = i;
    }
    else{
      merges(i, ma[pha[i]]);
    }
  }
  for(int i = 1; i <= N; ++i){
    if(!ma.count(ha[i])) continue;
    int u = finds(i);
    int v = finds(ma[ha[i]]);
    adj[u].eb(v); hpar[v] = true;
  }
  int res = 0;
  for(int i = 1; i <= N; ++i){
    if(i == finds(i)){
      if(!hpar[i]) res = max(res, dfs(i).fi);
    }
  }
  cout << res;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 11 ms 12160 KB Output is correct
4 Correct 577 ms 42232 KB Output is correct
5 Correct 53 ms 15224 KB Output is correct
6 Correct 22 ms 13508 KB Output is correct
7 Correct 20 ms 13348 KB Output is correct
8 Correct 20 ms 13280 KB Output is correct
9 Correct 67 ms 15748 KB Output is correct
10 Correct 18 ms 13320 KB Output is correct