Submission #94350

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
94350	2019-01-17T22:32:37 Z	jasony123123	Rima (COCI17_rima)	C++11	140 / 140	429 ms	113772 KB

rima

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e18;
/***************************COCI17 #4 P5 rima***********************************/

struct Node {
	int nxt[26];
	bool isEnd;
	Node() {
		memset(nxt, -1, sizeof nxt);
		isEnd = false;
	}
	v<int> getChildren() {
		v<int> chi;
		FOR(i, 0, 26) if (nxt[i] != -1) chi.push_back(nxt[i]);
		return chi;
	}
};

v<Node> trie(1);
int dp[3000009];
int tsz = 1;

void addTrieNode(string &s) {
	int cur = 0;
	for (char &c : s) {
		if (trie[cur].nxt[c - 'a'] == -1) {
			trie[cur].nxt[c - 'a'] = tsz++;
			trie.push_back(Node());
		}
		cur = trie[cur].nxt[c - 'a'];
	}
	trie[cur].isEnd = true;
}

void setupdp() {
	RFORE(i, tsz - 1, 0) {
		if (trie[i].isEnd == false) dp[i] = 0;
		else {
			v<int> c = trie[i].getChildren();
			int numEnd = 0, maxDp = 0;
			for (auto j : c) if (trie[j].isEnd) numEnd++, maxx(maxDp, dp[j]);
			dp[i] = 1 + max(0, numEnd - 1) + maxDp;
		}
	}
}

void input() {
	int n; cin >> n;
	FOR(i, 0, n) {
		string s; cin >> s;
		reverse(all(s));
		addTrieNode(s);
	}
}

int main() {
	io();
	input();
	setupdp();
//	darr(dp, tsz);
	int ans = 0;
	FOR(i, 0, tsz) {
		v<int> c = trie[i].getChildren();
		int numEnd = 0;
		pii maxdp = { 0,0 };
		for (auto j : c) if (trie[j].isEnd) {
			numEnd++;
			if (dp[j] > maxdp.second) maxdp.second = dp[j];
			if (maxdp.second > maxdp.first) swap(maxdp.first, maxdp.second);
		}

		// case 1
		maxx(ans, maxdp.first + maxdp.second + max(numEnd - 2, 0));

		// case 2
		if (trie[i].isEnd)
			maxx(ans, maxdp.first + maxdp.second + max(numEnd - 2, 0) + 1);
	}
	cout << ans << "\n";
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	429 ms	113772 KB	Output is correct
5	Correct	25 ms	3524 KB	Output is correct
6	Correct	103 ms	56860 KB	Output is correct
7	Correct	99 ms	56912 KB	Output is correct
8	Correct	103 ms	56584 KB	Output is correct
9	Correct	126 ms	58404 KB	Output is correct
10	Correct	100 ms	56624 KB	Output is correct