Submission #240080

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
240080	2020-06-18T00:52:04 Z	luciocf	Rima (COCI17_rima)	C++14	56 / 140	501 ms	139616 KB

rima

#include <bits/stdc++.h>

using namespace std;

const int maxn = 3e6+10;

struct Node
{
	Node *b[26];
	int u;
	bool fim;
};

int cnt;

int dp[maxn], path[maxn];

void add(Node *t, string s)
{
	Node *at = t;

	for (auto c: s)
	{
		if (!at->b[c-'a'])
		{
			at->b[c-'a'] = new Node();
			at->b[c-'a']->u = ++cnt;
		}

		at = at->b[c-'a'];
	}

	at->fim = true;
}

void dfs(Node *t)
{
	int mxdp = -1;
	int mx1 = -1, mx2 = -1;

	int tot = (t->fim);

	for (int i = 0; i < 26; i++)
	{
		if (!t->b[i]) continue;

		dfs(t->b[i]);

		if (t->b[i]->fim)
		{
			mxdp = max(mxdp, dp[t->b[i]->u]);
			tot++;

			int x = path[t->b[i]->u];

			if (x > mx1) mx2 = mx1, mx1 = x;
			else if (x > mx2) mx2 = x;
		}
	}

	dp[t->u] = tot;
	if (mxdp != -1) dp[t->u] = max(dp[t->u], mxdp + tot-1);

	if (mx2 != -1) 
	{
		dp[t->u] = max(mx1 + mx2 + tot-2, mxdp + tot-1);
		path[t->u] = mx1 + tot-1;
	}
	else if (mx1 != -1)
	{
		dp[t->u] = max(mx1 + tot-1, mxdp + tot-1);
		path[t->u] = mx1 + tot-1;
	}
}

int main(void)
{
	Node *root = new Node();
	root->u = 0;

	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
	{
		string s;
		cin >> s;

		reverse(s.begin(), s.end());

		add(root, s);
	}

	dfs(root);

	int ans = 0;
	for (int i = 0; i < maxn; i++)
		ans = max(ans, dp[i]);

	printf("%d\n", ans);
}

Compilation message

rima.cpp: In function 'int main()':
rima.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~

Subtask #1

56.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	384 KB	Output is correct
2	Correct	10 ms	384 KB	Output is correct
3	Correct	10 ms	384 KB	Output is correct
4	Incorrect	501 ms	139616 KB	Output isn't correct
5	Correct	152 ms	1016 KB	Output is correct
6	Incorrect	121 ms	91448 KB	Output isn't correct
7	Incorrect	115 ms	91332 KB	Output isn't correct
8	Incorrect	122 ms	91188 KB	Output isn't correct
9	Incorrect	253 ms	94516 KB	Output isn't correct
10	Incorrect	113 ms	91064 KB	Output isn't correct