Submission #473783

#	Time	Username	Problem	Language	Result	Execution time	Memory
473783		Killer2501	Rima (COCI17_rima)	C++14	140 / 140	651 ms	35872 KiB

rima

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define pll pair<ll, ll>
#define fi first
#define se second
#define ull unsigned long long
#define pb push_back
using namespace std;
const int N = 5e5+5;
const int M = 205;
const ll mod = 1e9+7;
const int base = 311;
ll n, m, a[N], b[N], c[N], tong, k, ans, d[N], fe[N], lab[N];
pll dp[N];
map<ll, ll> mp;
vector<ll> adj[N], kq;
string s;
ll pw(ll k, ll n)
{
	ll total = 1;
	for(; n; n >>= 1)
	{
		if(n & 1)total = total * k % mod;
		k = k * k % mod;
	}
	return total;
}
ll findp(ll u)
{
	return lab[u] < 0 ? u : lab[u] = findp(lab[u]);
}
void hop(ll u, ll v)
{
	if(lab[u] > lab[v])swap(lab[u], lab[v]);
	lab[u] += lab[v];
	lab[v] = u;
}
void dfs(ll u, ll p = -1)
{
	ll ok = (lab[u] != -1 && p != -1);
	dp[u].se = -lab[u];
	dp[u].fi = -lab[u] + ok;
	for(ll v: adj[u])
	{
		dfs(v, u);
		dp[u].fi = max(dp[u].fi, dp[v].fi);
		dp[u].fi = max(dp[u].fi, dp[v].se + dp[u].se + ok);
		dp[u].se = max(dp[u].se, dp[v].se - lab[u]);
	}

}
ll get(string s)
{
	ll total = 0;
	for(int i = 0; i < s.length(); i ++)total = (total * base+ s[i]-'a' + 1) % mod;
	return total;
}
void sol()
{

    cin >> n;
    fill_n(lab, n+1, -1);
    for(int i = 1; i <= n; i ++)
	{
		cin >> s;
		reverse(s.begin(), s.end());
		a[i] = get(s);
		s.pop_back();
		b[i] = get(s);
		if(mp[b[i]] > 0)
		{
			ll u = findp(i), v = findp(mp[b[i]]);
			hop(u, v);
		}
		else mp[b[i]] = i;
	}
	for(int i = 1; i <= n; i ++)
	{
		if(mp.count(a[i]))
		{
			ll u = findp(i), v = findp(mp[a[i]]);
			adj[u].pb(v);
			c[v] = 1;
		}
	}
	for(int i = 1; i <= n; i ++)
	{
		if(lab[i] < 0 && !c[i])
		{
			dfs(i);
			ans = max(ans, dp[i].fi);
		}
	}
	cout << ans;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "INSSORT"
    if(fopen(task".inp", "r"))
	{
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
    int test = 1;
    //cin >> test;
    while(test -- > 0)sol();
    return 0;
}
/*
1
4 11
2 6 14 18
0 3
4 5
11 15
3 5
10 13
16 16
1 4
8 12
17 19
7 13
14 19
*/

Compilation message (stderr)

rima.cpp: In function 'int get(std::string)':
rima.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(int i = 0; i < s.length(); i ++)total = (total * base+ s[i]-'a' + 1) % mod;
      |                 ~~^~~~~~~~~~~~
rima.cpp: In function 'int main()':
rima.cpp:105:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
rima.cpp:106:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 140 / 140