8.26T1 日记和最短路（二分 哈希 倍增）

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141575217

http://cplusoj.com/d/senior/p/NOD2301A

题解做法复杂度是错的，hack掉了

比较两个字符串常见方法是二分加hash

在这题套个倍增就行

题解做法也有可取的，把一个串拆成一堆小字符，实现起来方便很多

最后我打了9k

复杂度两只log

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCALd
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
 #define debag(...) fprintf(stderr, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
 #define debag(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
#define M 2000010
#define mo 998244353
#define N 100010
vector<int>G1[N], G2[N]; 
int eff[N], pw[M], Du[N]; 
int n, m, i, j, k, T;
string str; 
map<pair<int, int>, vector<string> >S1, S2; 
map<pair<int, int>, string>mp; 

void dfs_eff1(int x) {
	if(eff[x] & 1) return ; 
	eff[x] |= 1; 
	for(int y : G1[x]) dfs_eff1(y); 
}

void dfs_eff2(int x) {
	if(eff[x] & 2) return ; 
	eff[x] |= 2; 
	for(int y : G2[x]) dfs_eff2(y); 
}

namespace Sol2 {
	int f[N][22], g[N][22], L[N][22]; 
	vector<int>H[N], T[N]; 
	int len, Len;
	int h1[M], h2[M], t1[M], t2[M];	
	int nxt[N], dep[N], du[N]; 
	queue<int>q; 
	int merge(int x, int y, int l) {
		return (x * pw[l] + y) % mo; 
	}
	int Qry1(int x, int l) {
		if(l <= Len) return h1[l]; 
		int nw = h1[Len]; l -= Len; 
		for(k = 20; k >= 0; --k)
			if(f[x][k] && l >= L[x][k])  {
				nw = merge(nw, g[x][k], L[x][k]); 
				l -= L[x][k]; 
				x = f[x][k]; 
			}
		if(x == n) return nw; 
		assert(l <= L[x][0]); 
		nw = merge(nw, H[x][l], l); 
		return nw; 
	}
	int Qry2(int x, int l) {
		if(l <= len) return h2[l]; 
		int nw = h2[len]; l -= len; 
		for(k = 20; k >= 0; --k)
			if(f[x][k] && l >= L[x][k])  {
				nw = merge(nw, g[x][k], L[x][k]); 
				l -= L[x][k]; 
				x = f[x][k]; 
			}
		if(x == n) return nw; 
		assert(l <= L[x][0]); 
		nw = merge(nw, H[x][l], l); 
		return nw; 
	}
	int Qu1(int x, int l) {
		if(l <= Len) return t1[l]; 
		l -= Len; 
		for(k = 20; k >= 0; --k)
			if(f[x][k] && l > L[x][k])  {
				l -= L[x][k]; 
				x = f[x][k]; 
			}
		if(x == n) return 0; 
		debug("== %lld %lld %c %lld\n", x, l, (char)(T[x][l] + 'a' - 1), T[x][l]); 
		return T[x][l]; 
	}
	int Qu2(int x, int l) {
		if(l <= len) return t2[l]; 
		l -= len; 
		for(k = 20; k >= 0; --k)
			if(f[x][k] && l > L[x][k])  {
				l -= L[x][k]; 
				x = f[x][k]; 
			}
		if(x == n) return 0; 
		debug("== %lld %lld %c %lld\n", x, l, (char)(T[x][l] + 'a' - 1), T[x][l]); 
		return T[x][l]; 
	}
	int cmp(int x, int u, int v) {
		debug("%lld [%lld %lld]\n", x, u, v); 
		if(n <= 10) str = S2[{x, v}][S2[{x, v}].size() - 1], S2[{x, v}].pop_back(); 
		else str = mp[{x, v}]; 
		
		len = str.size(); 
//		debug("In %lld cmping(%lld %lld) %lld\n", x, u, v, len); 
		for(i = 0; i < len; ++i) {
			t2[i + 1] = str[i] - 'a' + 1; 
			h2[i + 1] = (h2[i] * 47 + t2[i + 1]) % mo; 
		}
		if(!u) {
			Len = len; 
			for(i = 1; i <= len; ++i) 
				h1[i] = h2[i], t1[i] = t2[i]; 
			return v; 
		}
//		if(dep[u] + Len < dep[v] + len) return u; 
//		assert(dep[u] + Len == dep[v] + len) ; 
		int l, r; l = 0; r = 100000; 
		while(l < r) { // lcp
			int mid = (l + r + 1) >> 1; 
////			debug("Today is %lld\n", mid); 
			int s1 = Qry1(u, mid); 
			int s2 = Qry2(v, mid);
			if(x == 1 && mid == 4)  debug("%lld %lld\n", s1, s2); 
			if(s1 == s2) l = mid; 
			else r = mid - 1; 
		}
		if(x == 1) debug("%lld[%lld %lld]\n", l, u, v); 
		int c1 = Qu1(u, l + 1); 
		int c2 = Qu2(v, l + 1); 
		debug("%lld %lld\n", c1, c2); 
		if(c2 < c1) {
			Len = len; 
			for(i = 1; i <= len; ++i) 
				h1[i] = h2[i], t1[i] = t2[i]; 
			swap(u, v); 
		}
		return u; 
	}
	void calc(int x) {
		H[x].resize(Len + 5); 
		T[x].resize(Len + 5); 
		for(i = 1; i <= Len; ++i) 
			H[x][i] = h1[i], T[x][i] = t1[i]; 
		dep[x] = dep[nxt[x]] + Len; 
		f[x][0] = nxt[x]; g[x][0] = H[x][Len]; L[x][0] = Len; 
		for(k = 1; k <= 20; ++k) {
			f[x][k] = f[f[x][k - 1]][k - 1]; 
			g[x][k] = merge(g[x][k - 1], g[f[x][k - 1]][k - 1], L[f[x][k - 1]][k - 1]); 
			L[x][k] = L[x][k - 1] + L[f[x][k - 1]][k - 1]; 
		}
	}
	void work(int x) {
		Len = 0; 
		for(int y : G1[x]) if(eff[y] == 3) {
			nxt[x] = cmp(x, nxt[x], y); 
		}
		calc(x); 
	}
	void print(int x) {
		if(!nxt[x]) return ; 
		for(i = 1; i <= L[x][0]; ++i) printf("%c", (char)(T[x][i] + 'a' - 1)); 
//		str = mp[{x, nxt[x]}]; cout << str; 
		print(nxt[x]); 
	}
	void main() {
		memcpy(du, Du, sizeof(Du)); q.push(n); 
		while(!q.empty()) {
			int u = q.front(); q.pop(); 
			for(int v : G2[u]) if(eff[v] == 3) {
				if(--du[v] == 0) work(v), q.push(v); 
			}
		}
//		print(6); debug("\n"); 
		print(1); 
	}
}

namespace Sol1 {
	int f[N][22], g[N][22], L[N][22]; 
	vector<int>H[N], T[N]; 
	int len, Len;
	int h1[M], h2[M], t1[M], t2[M];	
	int nxt[N], dep[N], du[N]; 
	queue<int>q; 
	int merge(int x, int y, int l) {
		return (x * pw[l] + y) % mo; 
	}
	int Qry1(int x, int l) {
		if(l <= Len) return h1[l]; 
		int nw = h1[Len]; l -= Len; 
		for(k = 20; k >= 0; --k)
			if(f[x][k] && l >= L[x][k])  {
				nw = merge(nw, g[x][k], L[x][k]); 
				l -= L[x][k]; 
				x = f[x][k]; 
			}
		if(x == n) return nw; 
		assert(l <= L[x][0]); 
		nw = merge(nw, H[x][l], l); 
		return nw; 
	}
	int Qry2(int x, int l) {
		if(l <= len) return h2[l]; 
		int nw = h2[len]; l -= len; 
		for(k = 20; k >= 0; --k)
			if(f[x][k] && l >= L[x][k])  {
				nw = merge(nw, g[x][k], L[x][k]); 
				l -= L[x][k]; 
				x = f[x][k]; 
			}
		if(x == n) return nw; 
		assert(l <= L[x][0]); 
		nw = merge(nw, H[x][l], l); 
		return nw; 
	}
	int Qu1(int x, int l) {
		if(l <= Len) return t1[l]; 
		l -= Len; 
		for(k = 20; k >= 0; --k)
			if(f[x][k] && l > L[x][k])  {
				l -= L[x][k]; 
				x = f[x][k]; 
			}
		if(x == n) return 0; 
		debug("== %lld %lld %c %lld\n", x, l, (char)(T[x][l] + 'a' - 1), T[x][l]); 
		return T[x][l]; 
	}
	int Qu2(int x, int l) {
		if(l <= len) return t2[l]; 
		l -= len; 
		for(k = 20; k >= 0; --k)
			if(f[x][k] && l > L[x][k])  {
				l -= L[x][k]; 
				x = f[x][k]; 
			}
		if(x == n) return 0; 
		debug("== %lld %lld %c %lld\n", x, l, (char)(T[x][l] + 'a' - 1), T[x][l]); 
		return T[x][l]; 
	}
	int cmp(int x, int u, int v) {
//		str = *S1[{x, v}].begin(); S1[{x, v}].erase(*S1[{x, v}].begin()); 
		if(n <= 10) str = S1[{x, v}][S1[{x, v}].size() - 1], S1[{x, v}].pop_back(); 
		else str = mp[{x, v}]; 
		len = str.size(); 
//		debug("In %lld cmping(%lld %lld) %lld\n", x, u, v, len); 
		for(i = 0; i < len; ++i) {
			t2[i + 1] = str[i] - 'a' + 1; 
			h2[i + 1] = (h2[i] * 47 + t2[i + 1]) % mo; 
		}
		if(!u || dep[u] + Len > dep[v] + len) {
			Len = len; 
			for(i = 1; i <= len; ++i) 
				h1[i] = h2[i], t1[i] = t2[i]; 
			return v; 
		}
		if(dep[u] + Len < dep[v] + len) return u; 
		assert(dep[u] + Len == dep[v] + len) ; 
		int l, r; l = 0; r = 100000; 
		while(l < r) { // lcp
			int mid = (l + r + 1) >> 1; 
////			debug("Today is %lld\n", mid); 
			int s1 = Qry1(u, mid); 
			int s2 = Qry2(v, mid);
			if(x == 1 && mid == 4)  debug("%lld %lld\n", s1, s2); 
			if(s1 == s2) l = mid; 
			else r = mid - 1; 
		}
		if(x == 1) debug("%lld[%lld %lld]\n", l, u, v); 
		int c1 = Qu1(u, l + 1); 
		int c2 = Qu2(v, l + 1); 
		debug("%lld %lld\n", c1, c2); 
		if(c2 < c1) {
			Len = len; 
			for(i = 1; i <= len; ++i) 
				h1[i] = h2[i], t1[i] = t2[i]; 
			swap(u, v); 
		}
		return u; 
	}
	void calc(int x) {
		H[x].resize(Len + 5); 
		T[x].resize(Len + 5); 
		for(i = 1; i <= Len; ++i) 
			H[x][i] = h1[i], T[x][i] = t1[i]; 
		dep[x] = dep[nxt[x]] + Len; 
		f[x][0] = nxt[x]; g[x][0] = H[x][Len]; L[x][0] = Len; 
		for(k = 1; k <= 20; ++k) {
			f[x][k] = f[f[x][k - 1]][k - 1]; 
			g[x][k] = merge(g[x][k - 1], g[f[x][k - 1]][k - 1], L[f[x][k - 1]][k - 1]); 
			L[x][k] = L[x][k - 1] + L[f[x][k - 1]][k - 1]; 
		}
	}
	void work(int x) {
		Len = 0; 
		for(int y : G1[x]) if(eff[y] == 3) {
			nxt[x] = cmp(x, nxt[x], y); 
		}
		calc(x); 
	}
	void print(int x) {
		if(!nxt[x]) return ; 
		for(i = 1; i <= L[x][0]; ++i) printf("%c", (char)(T[x][i] + 'a' - 1)); 
//		str = mp[{x, nxt[x]}]; cout << str; 
		print(nxt[x]); 
	}
	void main() {
		memcpy(du, Du, sizeof(Du)); q.push(n); 
		while(!q.empty()) {
			int u = q.front(); q.pop(); 
			for(int v : G2[u]) if(eff[v] == 3) {
				if(--du[v] == 0) work(v), q.push(v); 
			}
		}
//		print(6); debug("\n"); 

		print(1); 
	}
}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n = read(); m = read(); 
	if(n <= 10) {
		for(i = 1; i <= m; ++i) {
			int u, v; u = read(); v = read(); 
			assert(u != v); 
			G1[u].pb(v); G2[v].pb(u); 
			cin >> str; S1[{u, v}].pb(str); S2[{u, v}].pb(str); 
		}
	}
	else {
		for(i = 1; i <= m; ++i) {
			int u, v; u = read(); v = read(); 
			assert(u != v); 
			G1[u].pb(v); G2[v].pb(u); 
			cin >> str; mp[{u, v}] = str; 
		}
	}
	dfs_eff1(1); 
	dfs_eff2(n); 
	for(i = 1; i <= n; ++i) if(eff[i] == 3) {
		for(int y : G1[i]) if(eff[y] == 3) ++Du[i]; 
	}
	for(i = pw[0] = 1; i <= 2e6; ++i) pw[i] = pw[i - 1] * 47 % mo; 
	Sol1 :: main(); printf(" "); 
	Sol2 :: main(); 
	return 0;
}