제출 #676014

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
676014		as111	Rima (COCI17_rima)	C++14	126 / 140	186 ms	117676 KiB

rima

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

#define MAXN 25000

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: 126 / 140