Submission #879072

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
879072	2023-11-26T09:05:27 Z	serifefedartar	Rima (COCI17_rima)	C++17	140 / 140	245 ms	137356 KB

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.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	245 ms	137356 KB	Output is correct
5	Correct	13 ms	3932 KB	Output is correct
6	Correct	60 ms	86208 KB	Output is correct
7	Correct	59 ms	85960 KB	Output is correct
8	Correct	57 ms	85636 KB	Output is correct
9	Correct	71 ms	91256 KB	Output is correct
10	Correct	59 ms	85784 KB	Output is correct