General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
96931922 Practice:
qhqh
1437G - 15 C++17 (GCC 7-32) Accepted 467 ms 53352 KB 2020-10-27 20:36:24 2020-10-28 10:25:03
→ Source
#include <bits/stdc++.h>
using namespace std;

const int B = 26;
const int N = 3e5 + 10;
const int M = N * B;
const char O = 'a';

namespace acaho {
	int ch[N][B], link[N], nc;
	int root = 0;

	int vis[N];
	int endpos[N], val[N], ec;

	int np (void) {
		nc ++;
		fill(ch[nc], ch[nc] + B, 0);
		link[nc] = 0;
		val[nc] = -1;
		return nc;
	}

	void insert (char * s) {
		int p = root;
		for (int i = 0, o; s[i]; i ++) {
			if (!ch[p][o = s[i] - O]) ch[p][o] = np();
			p = ch[p][o];
		}
		val[p] = 0;
		endpos[++ ec] = p;
	}

	void build (void) {
		queue<int> q;
		for (int o = 0; o < B; o ++) if (ch[root][o])
			q.push(ch[root][o]);
		while (!q.empty()) {
			int p = q.front(); q.pop();
			for (int o = 0; o < B; o ++) {
				if (ch[p][o]) {
					link[ch[p][o]] = ch[link[p]][o];
					q.push(ch[p][o]);
				} else {
					ch[p][o] = ch[link[p]][o];
				}
			}
		}
	}

	void clear (void) { nc = -1; root = np(); }
};

using namespace acaho;

char s[N];
int value[N]; multiset<int> vs[N];

int main (void) {
	clear();

	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++) {
		scanf("%s", s);
		insert(s);
		vs[endpos[i]].insert(0);
	}
	build();
	int len = 0;
	for (int i = 1, opt, x, y; i <= m; i ++) {
		scanf("%d", &opt);
		if (opt == 1) {
			scanf("%d%d", &x, &y);
			vs[endpos[x]].erase(vs[endpos[x]].find(value[x]));
			vs[endpos[x]].insert(value[x] = y);
			val[endpos[x]] = *(--vs[endpos[x]].end());
		} else {
			scanf("%s", s);
			int ans = -1, p = 0;
			len += strlen(s);
			for (int j = 0; s[j]; j ++) {
				p = ch[p][s[j] - 'a'];
				for (int q = p; vis[q] != i && q; q = link[q]) {
					ans = max(ans, val[q]);
					vis[q] = i;
				}
			}
			printf("%d\n", ans);
		}
	}
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details