| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 473783 |
2021-09-16T08:51:31 Z |
Killer2501 |
Rima (COCI17_rima) |
C++14 |
|
651 ms |
35872 KB |
#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
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);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
11980 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11980 KB |
Output is correct |
| 3 |
Correct |
8 ms |
12072 KB |
Output is correct |
| 4 |
Correct |
651 ms |
35872 KB |
Output is correct |
| 5 |
Correct |
49 ms |
12356 KB |
Output is correct |
| 6 |
Correct |
18 ms |
12844 KB |
Output is correct |
| 7 |
Correct |
17 ms |
12784 KB |
Output is correct |
| 8 |
Correct |
15 ms |
12716 KB |
Output is correct |
| 9 |
Correct |
57 ms |
13136 KB |
Output is correct |
| 10 |
Correct |
15 ms |
12756 KB |
Output is correct |
