# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
380540 | SavicS | Rima (COCI17_rima) | C++14 | 103 ms | 39580 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 100005;
const int inf = 1e9 + 5;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k) print the k-th smallest number in os(0-based)
int n;
string s[maxn];
int dp[maxn];
int idx = 0;
int kraj[20*maxn];
int lipa[20*maxn][26];
void add(string a, int id){
int tr = 0;
ff(i,0,sz(a) - 1){
if(!lipa[tr][a[i] - 'a'])lipa[tr][a[i] - 'a'] = ++idx;
tr = lipa[tr][a[i] - 'a'];
}
kraj[tr] = max(kraj[tr], dp[id]);
}
int kve(string a){
int tr = 0;
int pomtr = -1;
int ide = 0;
ff(i,0,sz(a) - 1){
if(i == sz(a) - 1)pomtr = tr;
if(!lipa[tr][a[i] - 'a'])break;
ide = i;
tr = lipa[tr][a[i] - 'a'];
}
// gledam za jednu ispred
int ans = 0;
if(pomtr != -1){
ans = max(ans, kraj[pomtr]);
ff(i,0,25){
int ntr = lipa[pomtr][i];
if(ntr){
ans = max(ans, kraj[ntr]);
}
}
}
// gledam za jednu ispod
if(ide == sz(a) - 1){
ff(i,0,25){
int ntr = lipa[tr][i];
if(ntr)ans = max(ans, kraj[ntr]);
}
}
return ans;
}
bool cmp(string s1, string s2){
return sz(s1) < sz(s2);
}
int main()
{
ios::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
cin >> n;
ff(i,1,n)cin >> s[i];
sort(s + 1, s + n + 1, cmp);
int j = 0;
while(j + 1 <= n && sz(s[j + 1]) == 1)j += 1;
ff(i,1,j){
string x = s[i];
reverse(all(x));
dp[i] = j;
add(x, i);
}
ff(i,j + 1,n){
string x = s[i];
reverse(all(x));
dp[i] = kve(x) + 1;
add(x, i);
}
int rez = 0;
ff(i,1,n)rez = max(rez, dp[i]);
cout << rez << endl;
return 0;
}
/**
3
v
v
lwt
5
og
g
keaag
v
wlc
// probati bojenje sahovski ili slicno
**/
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |