Submission #676016

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
676016	2022-12-28T21:14:47 Z	as111	Rima (COCI17_rima)	C++14	140 / 140	258 ms	137912 KB

rima

//tries data structure, can be used for prefixes, etc.
#include <iostream>
#include <vector>

#define MAXN 50000

using namespace std;

struct Trie {
	int nex[26]; // index of next trie for each letter
	int prev; // parent
	bool end; // end of a word
	int mx; // max path
	Trie() {
		fill(nex, nex + 26, -1);
		prev = -1;
	}
};

Trie tries[MAXN * 20 + 5];
int N;
char letters[200];
int index = 1;
int ans = 0;
void traverse(int curr) {
	int children = 0;
	int maxchild = 0;
	int maxchild2 = 0; // top 2 max children
	for (int c = 0; c < 26; c++) { // loop through each letter
		int next = tries[curr].nex[c];
		if (next != -1) {
			traverse(next);
			if (tries[next].end) { // next is an end, otherwise don't connect to curr
				if (tries[next].mx > maxchild) {
					maxchild2 = maxchild;
					maxchild = tries[next].mx;
				}
				else if (tries[next].mx > maxchild2) {
					maxchild2 = tries[next].mx;
				}
				children++;
			}
		}
	}
	if (children > 1) {
		tries[curr].mx += maxchild + children - 1; // can visit all siblings before moving down to curr
		ans = max(ans, tries[curr].mx + maxchild2 - 1); // connect second longest path
	}
	else {
		tries[curr].mx += maxchild;
		ans = max(ans, tries[curr].mx);
	}
}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		int curr = 0;
		for (int j = (int)str.length() - 1; j >= 0;j--) {
			int c = (int)str[j] - 97;
			letters[c] = str[j];
			if (tries[curr].nex[c] != -1) { // prefix recorded previously
				curr = tries[curr].nex[c];
			}
			else {
				tries[curr].nex[c] = index;
				tries[index].prev = curr;
				curr = index;
				index++;
			}
		}
		tries[curr].end = true;
		tries[curr].mx = 1; // count word itself
	}
	traverse(0);
	cout << ans;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	113736 KB	Output is correct
2	Correct	45 ms	113784 KB	Output is correct
3	Correct	44 ms	113772 KB	Output is correct
4	Correct	258 ms	114652 KB	Output is correct
5	Correct	112 ms	114368 KB	Output is correct
6	Correct	91 ms	137808 KB	Output is correct
7	Correct	82 ms	137836 KB	Output is correct
8	Correct	87 ms	137792 KB	Output is correct
9	Correct	149 ms	137912 KB	Output is correct
10	Correct	83 ms	137908 KB	Output is correct