Submission #1186189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186189		kl0989e	Viruses (BOI20_viruses)	C++20	0 / 100	0 ms	328 KiB

Viruses

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

bool kmp(const vi& a, const vi& b) {
	int n=a.size();
	int m=b.size();
	vi table(m,0);
	int pt=0;
	for (int i=1; i<m; i++) {
		while (pt>0 && b[pt]!=b[i]) {
			pt=table[pt-1];
		}
		if (b[pt]==b[i]) {
			pt++;
		}
		table[i]=pt;
	}
	pt=0;
	for (int i=0; i<n; i++) {
		while (pt>0 && (pt==m || a[i]==b[pt])) {
			pt=table[pt-1];
		}
		if (a[i]==b[pt]) {
			pt++;
		}
		if (pt==m) {
			return 1;
		}
	}
	return 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	int g,n,m;
	cin >> g >> n >> m;
	vector<vector<vi>> ch(g);
	vi tin(g,0);
	vector<vi> out(g);
	int a,sz;
	for (int i=0; i<n; i++) {
		cin >> a >> sz;
		ch[a].pb(vi(sz));
		tin[a]+=sz;
		for (int j=0; j<sz; j++) {
			cin >> ch[a].back()[j];
			tin[a]-=ch[a].back()[j]<=1;
			if (ch[a].back()[j]>=2) {
				out[ch[a].back()[j]].pb(a);
			}
		}
	}
	vi has(g,0);
	vector<vi> ban(m);
	for (int i=0; i<m; i++) {
		cin >> sz;
		ban[i].resize(sz);
		for (int j=0; j<sz; j++) {
			cin >> ban[i][j];
		}
		if (ban[i].size()==1) {
			has[ban[i][0]]=1;
		}
	}
	vl sze(g,1e18);
	sze[0]=1;
	sze[1]=1;
	vector<vi> pref(g),suf(g);
	pref[0]={0};
	pref[1]={1};
	suf[0]={0};
	suf[1]={1};
	queue<int> q;
	for (int i=2; i<g; i++) {
		if (tin[i]==0) {
			q.push(i);
		}
	}
	while (q.size()) {
		int a=q.front();
		q.pop();
		for (auto s:out[a]) {
			tin[s]--;
			if (tin[s]==0) {
				q.push(s);
			}
		}
		sze[a]=0;
		vi cur;
		for (int i=0; i<ch[a][0].size(); i++) {
			has[a]|=has[ch[a][0][i]];
			sze[a]+=sze[ch[a][0][i]];
			for (auto aa:pref[ch[a][0][i]]) {
				cur.pb(aa);
			}
			if (pref[ch[a][0][i]].size()==50) {
				cur.pb(2);
				for (auto aa:suf[ch[a][0][i]]) {
					cur.pb(aa);
				}
			}
		}
		for (int i=0; i<m && !has[i]; i++) {
			has[a]|=kmp(cur,ban[i]);
		}
		int pt=0;
		while (pt<cur.size() && pref[a].size()<50) {
			pref[a].pb(cur[pt++]);
		}
		pt=max(0,(int)cur.size()-50);
		while (pt<cur.size() && suf[a].size()<50) {
			suf[a].pb(cur[pt++]);
		}
	}
	for (int i=2; i<g; i++) {
		if (sze[i]==1e18 || has[i]) {
			cout << "YES\n";
		}
		else {
			cout << "NO " << sze[i] << '\n';
		}
	}
    return 0;
}

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