Submission #601022

#	Time	Username	Problem	Language	Result	Execution time	Memory
601022		Arnch	Viruses (BOI20_viruses)	C++17	0 / 100	1 ms	340 KiB

Viruses

// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl

constexpr ll inf = 1e18, N = 1e3 + 10, mod = 1e9 + 9, pr = 1000696969;

ll dp[N], color[N];
string s[N];
bool mark[N], ex[N];
map<int, bool> mp;
vector<int> ind[N], val[N], topol, adj[N], radj[N];

void dfs(int x) {
	mark[x] = 1;
	for(auto j : adj[x]) {
		if(!mark[j]) dfs(j);
	}
	topol.push_back(x);
}
void sfd(int x, int c) {
	mark[x] = 1;
	color[x] = c;
	for(auto j : radj[x]) {
		if(!mark[j]) sfd(j, c);
	}
}

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);
    
	int g, n, m; cin >>g >>n >>m;
	for(int i = 0; i < n; i++) {
		int a, k; cin >>a >>k;
		for(int j = 0; j < k; j++) {
			int u; cin >>u;
			val[i].push_back(u);

			adj[a].push_back(u);
			radj[u].push_back(a);
		}
		ind[a].push_back(i);
	}
	for(int i = 0; i < m; i++) {
		int e; cin >>e;
		ll cur = 0;
		for(int j = 0; j < e; j++) {
			int u; cin >>u;
			if(u == 0) cur *= pr, cur += 1, cur %= mod;
			else cur *= pr, cur += 2, cur %= mod;
		}
		mp[cur] = 1;
	}

//	assert(n == g - 2);

	s[0] = '0', s[1] = '1';
	mark[0] = mark[1] = 1;

	for(int i = 2; i < g; i++) {
		if(!mark[i]) dfs(i);
	}
	memset(mark, 0, sizeof(mark));
	reverse(All(topol));
	int colorcnt = 0;
	for(auto i : topol) {
		if(!mark[i]) sfd(i, colorcnt++);
	}

	for(auto i : topol) {
		for(auto j : adj[i]) {
			if(j > 1) {
				if(color[j] == color[i] || color[j] < color[i]) {
					ex[i] = 1;
					break;
				}
			}
			s[i] += s[j];
		}
	}

	for(int j = 2; j < g; j++) {
		if(ex[j]) {
			cout<<"YES" <<endl;
			continue;
		}
		string ans = s[j];
		bool flag = 0;
		for(int i = 0; i < Sz(ans); i++) {
			ll cur = 0;
			bool rip = 0;
			for(int j = i; j < Sz(ans); j++) {
				cur *= pr;
				if(ans[j] == '0') cur += 1;
				else cur += 2;
				cur %= mod;
				if(mp[cur]) {
					rip = 1;
					break;
				}
			}
			if(rip) {
				flag = 1;
				cout<<"YES" <<endl;
				break;
			}
		}
		if(!flag)
			cout<<"NO" <<" " <<Sz(ans) <<endl;
	}


	return 0;
}

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