Submission #226611

#	Time	Username	Problem	Language	Result	Execution time	Memory
226611		quocnguyen1012	Rima (COCI17_rima)	C++14	140 / 140	577 ms	42232 KiB

rima

#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 / 140