Submission #1253652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253652		nhnguyen14	Rima (COCI17_rima)	C++20	140 / 140	301 ms	212848 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)4e6;

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

vector<int>ke[MAXM+2];
	void add_canh(int u,int v){
		ke[u].push_back(v);
		return;
	}

	vector<Node> node;
	void load_size(){
		node.push_back(Node());
		return;
	}
	
	void insert_string(string &s,int val){
		int root = 0;
		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();
				add_canh(root , node[root].child[c]);
				node.push_back(Node());
			}
			root = node[root].child[c];
		}
		node[root].exist = true;
		return;
	}

int n;
int id[N+2] = {} , dp[MAXM+2] = {} ;
int ans = 0;
	void dfs(int u,int p){
		int mx1 = 0 , mx2 = 0;
		int sum_child = 0;
		for(auto& v : ke[u]){
			if (v==p) continue;	
			dfs(v,u);
			sum_child += node[v].exist;
			if (node[v].exist==false) continue;
			if (mx1 < dp[v]) {
				mx2 = mx1;
				mx1 = dp[v];
			}
			else maximize(mx2 , dp[v]);
		}
		maximize(ans , sum_child);
		if (node[u].exist) dp[u] = 1 + mx1 + max(0,sum_child-1);
		maximize(ans , max(0,sum_child-1) + mx1 + node[u].exist);
		maximize(ans , max(0 , sum_child - 2) + mx1 + mx2 + node[u].exist);
	}

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;
		load_size();
		FOR(i,1,n) {
			string s;
			cin >> s;
			reverse(s.begin() , s.end());
			insert_string(s,1);
		}
		dfs(0,0);
		cout<<ans;
}

Compilation message (stderr)

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

• Subtask 1: 140 / 140