Submission #254797

#	Time	Username	Problem	Language	Result	Execution time	Memory
254797		model_code	Viruses (BOI20_viruses)	C++17	100 / 100	171 ms	21624 KiB

Viruses

// O(K * L^3 * log)

#include <bits/stdc++.h>

using namespace std;

const int MK = 1000, ML = 51;

namespace AhoCorasick {
	struct node {
		int next[2];
		bool leaf;
		int p;
		char pch;
		int link;
		int go[2];
	};
	
	node t[ML + 1];
	int sz;
	
	void readString() {
		int len;
		ignore = scanf("%d", &len);
		
		int v = 0;
		for (int i = 0, c; i < len; i++) {
			ignore = scanf("%d", &c);
			
			if (t[v].next[c] == -1) {
				memset(t[sz].next, -1, sizeof t[sz].next);
				memset(t[sz].go, -1, sizeof t[sz].go);
				t[sz].link = -1;
				t[sz].p = v;
				t[sz].pch = c;
				t[v].next[c] = sz++;
			}
			
			v = t[v].next[c];
		}
		
		t[v].leaf = true;
	}
	
	int go(int v, int c);
	
	int get_link(int v) {
		if (t[v].link == -1) {
			if (v == 0 || t[v].p == 0) t[v].link = 0;
			else t[v].link = go(get_link(t[v].p), t[v].pch);
		
			get_link(t[v].link);
			if (t[t[v].link].leaf) t[v].leaf = true;
		}
		
		return t[v].link;
	}

	int go(int v, int c) {
		if (t[v].go[c] == -1) {
			if (t[v].next[c] != -1) t[v].go[c] = t[v].next[c];
			else t[v].go[c] = v == 0 ? 0 : go(get_link(v), c);
		}
		
		return t[v].go[c];
	}
	
	int to[ML][2];
	int create(int m) {
		t[0].p = t[0].link = -1;
		memset(t[0].next, -1, sizeof t[0].next);
		memset(t[0].go, -1, sizeof t[0].go);
		sz = 1;
		
		for (int i = 0; i < m; i++) readString();
		
		int cnt = 0;
		map<int, int> mp;
		for (int i = 0; i < sz; i++) {
			get_link(i);
			if (t[i].leaf) continue;
			
			mp[i] = cnt++;
		}
		
		for (auto p : mp) {
			int v = p.first;
			for (int c = 0; c < 2; c++) {
				int u = go(v, c);
				if (t[u].leaf) to[p.second][c] = -1;
				else to[p.second][c] = mp[u];
			}
		}
		
		return cnt;
	}
}

typedef unsigned long long ull;

struct Int {
	static const ull INF;
	
	ull x;
	
	Int(ull x = INF) : x(x) { }
	
	Int operator + (const Int& rhs) const {
		if (x == INF || rhs.x == INF) return INF;
		
		return min(x + rhs.x, INF);
	}
	
	bool operator < (const Int& rhs) const {
		if (x == INF) return false;
		if (rhs.x == INF) return true;
		return x < rhs.x;
	}
};

const ull Int::INF = 1ULL << 63;

int a[MK], b[3 * MK], firstB[MK], lastB[MK];
vector<int> mutations[MK];

void simplifyMutations(int& n, int g) {
	int it = lastB[n - 1];
	
	for (int i = 0; i < n; i++) {
		int k = lastB[i] - firstB[i];
		if (k <= 2) continue;
		
		a[n] = g;
		firstB[n] = firstB[i];
		lastB[n] = lastB[i] - 1;
		
		firstB[i] = it;
		b[it++] = g;
		b[it++] = b[lastB[i] - 1];
		lastB[i] = it;
		
		g++;
		n++;
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = firstB[i]; j < lastB[i]; j++) {
			mutations[b[j]].push_back(i);
		}
	}
}

int L;
Int dp[MK][ML][ML];
set<tuple<ull, int, int, int>> S;

void update(int f, int s, int e, const Int& val) {
	if (val < dp[f][s][e]) {
		if (dp[f][s][e].x != Int::INF) {
			S.erase(make_tuple(dp[f][s][e].x, f, s, e));
		}
		
		dp[f][s][e] = val;
		
		S.emplace(val.x, f, s, e);
	}
}

void recalcMutationFast(int mut, int f, int s, int e) {
	int x = a[mut];
	int y = b[firstB[mut]];

	int k = lastB[mut] - firstB[mut];
	if (k == 1) {
		update(x, s, e, dp[y][s][e]);
		
		return;
	}
	
	assert(k == 2);
	
	int z = b[firstB[mut] + 1];
	
	if (y == f) {
		for (int t = 0; t < L; t++) {
			update(x, s, t, dp[y][s][e] + dp[z][e][t]);
		}
	}
	
	if (z == f) {
		for (int t = 0; t < L; t++) {
			update(x, t, e, dp[y][t][s] + dp[z][s][e]);
		}
	}
}

int main() {
	int g, n, m;
	ignore = scanf("%d %d %d", &g, &n, &m);
	
	for (int i = 0, it = 0, k; i < n; i++) {
		ignore = scanf("%d %d", a + i, &k);
		
		firstB[i] = it;
		for (int j = 0; j < k; j++) {
			ignore = scanf("%d", b + (it++));
		}
		
		lastB[i] = it;
	}
	
	simplifyMutations(n, g);
	
	L = AhoCorasick::create(m);
	
	for (int s = 0; s < L; s++) {
		for (int c = 0; c < 2; c++) {
			if (AhoCorasick::to[s][c] == -1) continue;
			
			update(c, s, AhoCorasick::to[s][c], 1);
		}
	}
	
	while (S.empty() == false) {
		int f, s, e;
		tie(ignore, f, s, e) = *S.begin();
		
		S.erase(S.begin());
		
		for (int i : mutations[f]) recalcMutationFast(i, f, s, e);
	}
	
	for (int i = 2; i < g; i++) {
		Int ans;
		for (int s = 0; s < L; s++)
			for (int e = 0; e < L; e++)
				ans = min(dp[i][s][e], ans);
		
		if (ans.x == Int::INF) printf("%s\n", "YES");
		else printf("%s %llu\n", "NO", ans.x);
	}
	
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 32 / 32
• Subtask 5: 18 / 18