Submission #1253540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253540		nhnguyen14	Rima (COCI17_rima)	C++20	56 / 140	233 ms	215476 KiB

rima

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define ii pair<int,int>
#define BIT(mask,x) (((mask)>>(x))&(1))
#define MASK(x) ((LL)(1)<<(x))
#define FOR(i,a,b) for(int i = (a),_b=(b); i<=_b;++i)
#define FORD(i,a,b) for(int i =(a),_b=(b);i>=_b;--i)

template<class X,class Y>
	bool maximize(X &x,Y y){
		if (x<y) return x=y,true; else return false;
	}
template<class X,class Y>
	bool minimize(X &x,Y y){
		if (x>y) return x=y,true; else return false;
	}

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
	int Rand(int l,int r){
		return uniform_int_distribution<int>(l,r)(rng);
	}
	
const int N = (int) 5e5;
const int MAXM = (int)3e6;
	string s[N+2];

struct Node{
	int child[26] = {};
	int exist = 0;
	LL cnt = 0;
	Node(){
		memset(child,-1,sizeof child);
		exist = 0;
		cnt = 0;
		return;
	}
};

class Trie{
public:
	vector<Node> node;
	void load_size(){
		node.push_back(Node());
		return;
	}
	void tmp_add(string &s,int val){
		int root = 0;
		for(int i = 0; i < (int)s.size() - 1; ++i){
			int c = s[i] - 'a';
			if (node[root].child[c] == -1){
				node[root].child[c] = node.size();
				node.push_back(Node());
			}
			root = node[root].child[c];
		}
		node[root].cnt += val;
		return;
	}
	int Get_cnt(string &s){
		int sum = 0 , root = 0;
		for(int i = 0; i < (int)s.size() - 1; ++i){
			int c = s[i] - 'a';
			if (node[root].child[c] == -1) return -1;
			root = node[root].child[c];
		}
		return node[root].cnt ;
	}
	void insert_string(string &s,int val){
		int root = 0;
		if (s.size()==1) maximize(node[0].exist,val);
		for(int i = 0; i < (int)s.size(); ++i){
			int c = s[i] - 'a';
			if (node[root].child[c]==-1) {
				node[root].child[c] = node.size();
				node.push_back(Node());
			}
			root = node[root].child[c];
			if (i >= (int)s.size() - 2) maximize(node[root].exist,val);	
		}
		return;
	}
	int Get(string &s){
		int sum = 0 , root = 0;
		if (s.size()==1) sum = node[0].exist;
		for(int i = 0; i < (int)s.size(); ++i){
			int c = s[i] - 'a';
			if (node[root].child[c]==-1) return sum;
			root = node[root].child[c];
			if (i >= (int)s.size() - 2) maximize(sum , node[root].exist);
		}
		return sum;
	}
};
Trie st;

int n;
int dp[N+2] = {} ;
vector<int>v[MAXM+2];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ;
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin >> n;
		st.load_size();
		FOR(i,1,n) {
			cin >> s[i];
			reverse(s[i].begin() , s[i].end());
			v[s[i].size()].push_back(i);
		}
		FOR(i,1,MAXM){
			for(auto x : v[i]) st.tmp_add(s[x] , 1);
			for(auto x : v[i]){
				int x_cnt = st.Get_cnt(s[x]);
				maximize(dp[x] , st.Get(s[x]) + x_cnt);
			}
			for(auto x : v[i]) {
				st.tmp_add(s[x] , -1);
				st.insert_string(s[x] , dp[x]);
			}
		}
		cout<<*max_element(dp+1,dp+n+1);
}

Compilation message (stderr)

rima.cpp: In function 'int main()':
rima.cpp:107:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
rima.cpp:108:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 56 / 140