Submission #879072

#	Time	Username	Problem	Language	Result	Execution time	Memory
879072		serifefedartar	Rima (COCI17_rima)	C++17	140 / 140	245 ms	137356 KiB

rima

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

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 9;
const ll LOGN = 21;
const ll MAXN = 1e6 + 100;

struct Node {
	Node *to[26];
	int one_path, term;
	Node() { 
		for (int i = 0; i < 26; i++)
			to[i] = NULL;
		one_path = 0, term = 0;
	}
};

int ans = 0;
void dfs(Node *now) {
	pair<int,int> p = {0, 0};

	int ch = 0;
	for (int i = 0; i < 26; i++) {
		if (now->to[i] == NULL)
			continue;
		dfs(now->to[i]);

		if (now->to[i]->term == 0)
			continue;

		int Q = now->to[i]->one_path;
		if (Q > p.f)
			p = {Q, p.f};
		else if (Q > p.s)
			p = {p.f, Q}; 
		ch++;
	}

	if (ch > 1) {
		now->one_path = p.f + ch + now->term - 1;
		ans = max(ans, now->one_path + p.s - 1);
	} else {
		now->one_path = p.f + now->term;
		ans = max(ans, p.f + now->term);
	}
}

int main() {
	fast
	int N;
	cin >> N;

	Node *root = new Node();
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		reverse(s.begin(), s.end());

		Node *now = root;
		for (auto u : s) {
			if (now->to[u-'a'] == NULL)
				now->to[u-'a'] = new Node();
			now = now->to[u-'a'];
		}
		now->term = 1;
	}
	dfs(root);
	cout << ans << "\n";
}

• Subtask 1: 140 / 140