제출 #530130

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
530130		fatemetmhr	Viruses (BOI20_viruses)	C++17	100 / 100	37 ms	6788 KiB

Viruses

//  ~Be name khoda~  //

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxg  =  200   + 15;
const int maxnf =  50    + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;

vector <pair<int, pair<int, bool>>> upd[maxg];
int nxt[maxnf][2], f[maxnf], newnode = 1, newgen;
ll dp[maxg][maxnf][maxnf];
bool bad[maxnf];
string s;
queue <int> q;
set <pair<ll, pair<int, pair<int, int>>>> av;


inline void make_edge(int a, int k){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int v; cin >> v;
	if(k == 1){
		upd[v].pb({a, {-1, 0}});
		return;
	}
	if(k == 2){
		int u; cin >> u;
		upd[u].pb({a, {v, 1}});
		upd[v].pb({a, {u, 0}});
		return;
	}
	int z = newgen++;
	upd[z].pb({a, {v, 1}});
	upd[v].pb({a, {z, 0}});
	make_edge(z, k - 1);
	return;
}

inline void add(){
	int v = 0;
	for(auto c : s){
		if(nxt[v][c - '0'] == 0) nxt[v][c - '0'] = newnode++;
		v = nxt[v][c - '0'];
	}
	bad[v] = true;
	return;
}
inline void aho(){
	q.push(0);
	while(!q.empty()){
		int v = q.front();
		q.pop();
		for(int i = 0; i < 2; i++){
			if(nxt[v][i] == 0) nxt[v][i] = nxt[f[v]][i];
			else{
				q.push(nxt[v][i]);
				f[nxt[v][i]] = v == 0 ? 0 : nxt[f[v]][i];
				bad[nxt[v][i]] |= bad[f[nxt[v][i]]];
			}
		}
	}
	return;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int g, n, m; cin >> g >> n >> m;
	newgen = g;
	for(int i = 0; i < n; i++){
		int k, a; cin >> a >> k;
		make_edge(a, k);
	}
	
	for(int i = 0; i < m; i++){
		int l; cin >> l;
		s = "";
		for(int i = 0; i < l; i++){
			char c; cin >> c;
			s.pb(c);
		}
		add();
	}
	aho();
	
	memset(dp, 63, sizeof(dp));
	ll yes = dp[0][0][0];
	
	for(int i = 0; i < newnode; i++) if(!bad[i]){
		pair <int, pair<int, int>> id1, id2;
		id1.fi = 0; id1.se.fi = i; id1.se.se = nxt[i][0];
		id2.fi = 1; id2.se.fi = i; id2.se.se = nxt[i][1];
		if(!bad[nxt[i][0]]) dp[0][i][nxt[i][0]] = 1, av.insert({1, id1});
		if(!bad[nxt[i][1]]) dp[1][i][nxt[i][1]] = 1, av.insert({1, id2});
	}
	
	while(!av.empty()){
		auto id = av.begin() -> se;
		av.erase(av.begin());
		int v = id.fi, st = id.se.fi, en = id.se.se;
		for(auto [u, p] : upd[v]){
			if(p.fi == -1){
				if(dp[u][st][en] <= dp[v][st][en]) continue;
				av.erase({dp[u][st][en], {u, {st, en}}});
				dp[u][st][en] = dp[v][st][en];	
				av.insert({dp[u][st][en], {u, {st, en}}});
			}
			else{
				int z = p.fi;
				for(int k = 0; k < newnode; k++){
					if(p.se){
						if(dp[z][k][st] + dp[v][st][en] >= dp[u][k][en])
							continue;
						av.erase({dp[u][k][en], {u, {k, en}}});
						dp[u][k][en] = dp[z][k][st] + dp[v][st][en];	
						av.insert({dp[u][k][en], {u, {k, en}}});
					}
					else{
						if(dp[v][st][en] + dp[z][en][k] >= dp[u][st][k])
							continue;
						av.erase({dp[u][st][k], {u, {st, k}}});
						dp[u][st][k] = dp[v][st][en] + dp[z][en][k];	
						av.insert({dp[u][st][k], {u, {st, k}}});
					}
				}
			}
		}
	}
	
	for(int i = 2; i < g; i++){
		ll ans = yes;
		for(int j = 0; j < newnode; j++)
			ans = min(ans, dp[i][0][j]);
		if(ans == yes) cout << "YES\n";
		else cout << "NO " << ans << '\n';
	} 
}

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