oj.uz

Submission #530130

# Submission time Handle Problem Language Result Execution time Memory
530130 2022-02-24T16:32:26 Z fatemetmhr Viruses (BOI20_viruses) C++17
100 / 100
 37 ms 6788 KB 
//  ~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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6344 KB Output is correct
2 Correct 3 ms 6344 KB Output is correct
3 Correct 3 ms 6352 KB Output is correct
4 Correct 3 ms 6344 KB Output is correct
5 Correct 3 ms 6352 KB Output is correct
6 Correct 3 ms 6352 KB Output is correct
7 Correct 3 ms 6340 KB Output is correct
8 Correct 3 ms 6352 KB Output is correct
9 Correct 3 ms 6352 KB Output is correct
10 Correct 3 ms 6352 KB Output is correct
11 Correct 3 ms 6352 KB Output is correct
12 Correct 3 ms 6352 KB Output is correct
13 Correct 3 ms 6352 KB Output is correct
14 Correct 3 ms 6352 KB Output is correct
15 Correct 3 ms 6352 KB Output is correct
16 Correct 3 ms 6352 KB Output is correct
17 Correct 3 ms 6352 KB Output is correct
18 Correct 3 ms 6352 KB Output is correct
19 Correct 3 ms 6352 KB Output is correct
20 Correct 3 ms 6352 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6344 KB Output is correct
2 Correct 3 ms 6344 KB Output is correct
3 Correct 4 ms 6352 KB Output is correct
4 Correct 3 ms 6352 KB Output is correct
5 Correct 3 ms 6352 KB Output is correct
6 Correct 3 ms 6352 KB Output is correct
7 Correct 3 ms 6352 KB Output is correct
8 Correct 3 ms 6352 KB Output is correct
9 Correct 3 ms 6352 KB Output is correct
10 Correct 3 ms 6368 KB Output is correct
11 Correct 3 ms 6352 KB Output is correct
12 Correct 3 ms 6352 KB Output is correct
13 Correct 3 ms 6352 KB Output is correct
14 Correct 3 ms 6352 KB Output is correct
15 Correct 3 ms 6352 KB Output is correct
16 Correct 3 ms 6280 KB Output is correct
17 Correct 3 ms 6360 KB Output is correct
18 Correct 3 ms 6344 KB Output is correct
19 Correct 3 ms 6352 KB Output is correct
20 Correct 3 ms 6352 KB Output is correct
21 Correct 3 ms 6352 KB Output is correct
22 Correct 3 ms 6352 KB Output is correct
23 Correct 3 ms 6348 KB Output is correct
24 Correct 3 ms 6352 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6352 KB Output is correct
2 Correct 3 ms 6352 KB Output is correct
3 Correct 3 ms 6352 KB Output is correct
4 Correct 3 ms 6352 KB Output is correct
5 Correct 3 ms 6352 KB Output is correct
6 Correct 3 ms 6352 KB Output is correct
7 Correct 3 ms 6352 KB Output is correct
8 Correct 3 ms 6352 KB Output is correct
9 Correct 3 ms 6352 KB Output is correct
10 Correct 4 ms 6340 KB Output is correct
11 Correct 3 ms 6352 KB Output is correct
12 Correct 3 ms 6352 KB Output is correct
13 Correct 3 ms 6352 KB Output is correct
14 Correct 3 ms 6352 KB Output is correct
15 Correct 3 ms 6352 KB Output is correct
16 Correct 3 ms 6348 KB Output is correct
17 Correct 3 ms 6352 KB Output is correct
18 Correct 3 ms 6344 KB Output is correct
19 Correct 3 ms 6352 KB Output is correct
20 Correct 3 ms 6352 KB Output is correct
21 Correct 3 ms 6352 KB Output is correct
22 Correct 3 ms 6352 KB Output is correct
23 Correct 3 ms 6352 KB Output is correct
24 Correct 3 ms 6340 KB Output is correct
25 Correct 7 ms 6480 KB Output is correct
26 Correct 3 ms 6352 KB Output is correct
27 Correct 37 ms 6660 KB Output is correct
28 Correct 4 ms 6352 KB Output is correct
29 Correct 36 ms 6340 KB Output is correct
30 Correct 34 ms 6352 KB Output is correct
31 Correct 7 ms 6420 KB Output is correct
32 Correct 5 ms 6352 KB Output is correct
33 Correct 4 ms 6340 KB Output is correct
34 Correct 30 ms 6352 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6344 KB Output is correct
2 Correct 3 ms 6344 KB Output is correct
3 Correct 3 ms 6352 KB Output is correct
4 Correct 3 ms 6344 KB Output is correct
5 Correct 3 ms 6352 KB Output is correct
6 Correct 3 ms 6352 KB Output is correct
7 Correct 3 ms 6340 KB Output is correct
8 Correct 3 ms 6352 KB Output is correct
9 Correct 3 ms 6352 KB Output is correct
10 Correct 3 ms 6352 KB Output is correct
11 Correct 3 ms 6352 KB Output is correct
12 Correct 3 ms 6352 KB Output is correct
13 Correct 3 ms 6352 KB Output is correct
14 Correct 3 ms 6352 KB Output is correct
15 Correct 3 ms 6352 KB Output is correct
16 Correct 3 ms 6352 KB Output is correct
17 Correct 3 ms 6352 KB Output is correct
18 Correct 3 ms 6352 KB Output is correct
19 Correct 3 ms 6352 KB Output is correct
20 Correct 3 ms 6352 KB Output is correct
21 Correct 3 ms 6368 KB Output is correct
22 Correct 3 ms 6352 KB Output is correct
23 Correct 3 ms 6352 KB Output is correct
24 Correct 4 ms 6340 KB Output is correct
25 Correct 3 ms 6352 KB Output is correct
26 Correct 3 ms 6352 KB Output is correct
27 Correct 3 ms 6352 KB Output is correct
28 Correct 3 ms 6352 KB Output is correct
29 Correct 3 ms 6352 KB Output is correct
30 Correct 3 ms 6348 KB Output is correct
31 Correct 3 ms 6352 KB Output is correct
32 Correct 3 ms 6344 KB Output is correct
33 Correct 3 ms 6352 KB Output is correct
34 Correct 3 ms 6352 KB Output is correct
35 Correct 3 ms 6352 KB Output is correct
36 Correct 3 ms 6352 KB Output is correct
37 Correct 3 ms 6352 KB Output is correct
38 Correct 3 ms 6340 KB Output is correct
39 Correct 3 ms 6352 KB Output is correct
40 Correct 3 ms 6352 KB Output is correct
41 Correct 3 ms 6352 KB Output is correct
42 Correct 3 ms 6352 KB Output is correct
43 Correct 3 ms 6352 KB Output is correct
44 Correct 3 ms 6352 KB Output is correct
45 Correct 3 ms 6352 KB Output is correct
46 Correct 2 ms 6352 KB Output is correct
47 Correct 3 ms 6352 KB Output is correct
48 Correct 4 ms 6344 KB Output is correct
49 Correct 3 ms 6352 KB Output is correct
50 Correct 3 ms 6352 KB Output is correct
51 Correct 3 ms 6352 KB Output is correct
52 Correct 3 ms 6352 KB Output is correct
53 Correct 3 ms 6352 KB Output is correct
54 Correct 4 ms 6352 KB Output is correct
55 Correct 3 ms 6352 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6344 KB Output is correct
2 Correct 3 ms 6344 KB Output is correct
3 Correct 3 ms 6352 KB Output is correct
4 Correct 3 ms 6344 KB Output is correct
5 Correct 3 ms 6352 KB Output is correct
6 Correct 3 ms 6352 KB Output is correct
7 Correct 3 ms 6340 KB Output is correct
8 Correct 3 ms 6352 KB Output is correct
9 Correct 3 ms 6352 KB Output is correct
10 Correct 3 ms 6352 KB Output is correct
11 Correct 3 ms 6352 KB Output is correct
12 Correct 3 ms 6352 KB Output is correct
13 Correct 3 ms 6352 KB Output is correct
14 Correct 3 ms 6352 KB Output is correct
15 Correct 3 ms 6352 KB Output is correct
16 Correct 3 ms 6352 KB Output is correct
17 Correct 3 ms 6352 KB Output is correct
18 Correct 3 ms 6352 KB Output is correct
19 Correct 3 ms 6352 KB Output is correct
20 Correct 3 ms 6352 KB Output is correct
21 Correct 4 ms 6352 KB Output is correct
22 Correct 3 ms 6352 KB Output is correct
23 Correct 3 ms 6352 KB Output is correct
24 Correct 3 ms 6352 KB Output is correct
25 Correct 3 ms 6352 KB Output is correct
26 Correct 3 ms 6352 KB Output is correct
27 Correct 3 ms 6352 KB Output is correct
28 Correct 3 ms 6368 KB Output is correct
29 Correct 3 ms 6352 KB Output is correct
30 Correct 3 ms 6352 KB Output is correct
31 Correct 3 ms 6352 KB Output is correct
32 Correct 3 ms 6352 KB Output is correct
33 Correct 3 ms 6352 KB Output is correct
34 Correct 3 ms 6280 KB Output is correct
35 Correct 3 ms 6360 KB Output is correct
36 Correct 3 ms 6344 KB Output is correct
37 Correct 3 ms 6352 KB Output is correct
38 Correct 3 ms 6352 KB Output is correct
39 Correct 3 ms 6352 KB Output is correct
40 Correct 3 ms 6352 KB Output is correct
41 Correct 3 ms 6348 KB Output is correct
42 Correct 3 ms 6352 KB Output is correct
43 Correct 3 ms 6352 KB Output is correct
44 Correct 3 ms 6352 KB Output is correct
45 Correct 4 ms 6340 KB Output is correct
46 Correct 3 ms 6352 KB Output is correct
47 Correct 3 ms 6352 KB Output is correct
48 Correct 3 ms 6352 KB Output is correct
49 Correct 3 ms 6352 KB Output is correct
50 Correct 3 ms 6352 KB Output is correct
51 Correct 3 ms 6348 KB Output is correct
52 Correct 3 ms 6352 KB Output is correct
53 Correct 3 ms 6344 KB Output is correct
54 Correct 3 ms 6352 KB Output is correct
55 Correct 3 ms 6352 KB Output is correct
56 Correct 3 ms 6352 KB Output is correct
57 Correct 3 ms 6352 KB Output is correct
58 Correct 3 ms 6352 KB Output is correct
59 Correct 3 ms 6340 KB Output is correct
60 Correct 7 ms 6480 KB Output is correct
61 Correct 3 ms 6352 KB Output is correct
62 Correct 37 ms 6660 KB Output is correct
63 Correct 4 ms 6352 KB Output is correct
64 Correct 36 ms 6340 KB Output is correct
65 Correct 34 ms 6352 KB Output is correct
66 Correct 7 ms 6420 KB Output is correct
67 Correct 5 ms 6352 KB Output is correct
68 Correct 4 ms 6340 KB Output is correct
69 Correct 30 ms 6352 KB Output is correct
70 Correct 3 ms 6352 KB Output is correct
71 Correct 3 ms 6352 KB Output is correct
72 Correct 3 ms 6352 KB Output is correct
73 Correct 3 ms 6352 KB Output is correct
74 Correct 3 ms 6352 KB Output is correct
75 Correct 3 ms 6352 KB Output is correct
76 Correct 3 ms 6352 KB Output is correct
77 Correct 2 ms 6352 KB Output is correct
78 Correct 3 ms 6352 KB Output is correct
79 Correct 4 ms 6344 KB Output is correct
80 Correct 3 ms 6352 KB Output is correct
81 Correct 3 ms 6352 KB Output is correct
82 Correct 3 ms 6352 KB Output is correct
83 Correct 3 ms 6352 KB Output is correct
84 Correct 3 ms 6352 KB Output is correct
85 Correct 4 ms 6352 KB Output is correct
86 Correct 3 ms 6352 KB Output is correct
87 Correct 8 ms 6480 KB Output is correct
88 Correct 3 ms 6352 KB Output is correct
89 Correct 3 ms 6348 KB Output is correct
90 Correct 3 ms 6352 KB Output is correct
91 Correct 3 ms 6352 KB Output is correct
92 Correct 29 ms 6788 KB Output is correct
93 Correct 26 ms 6760 KB Output is correct
94 Correct 3 ms 6352 KB Output is correct
95 Correct 3 ms 6352 KB Output is correct
96 Correct 3 ms 6352 KB Output is correct
97 Correct 10 ms 6428 KB Output is correct
98 Correct 3 ms 6352 KB Output is correct
99 Correct 9 ms 6352 KB Output is correct
100 Correct 3 ms 6344 KB Output is correct
101 Correct 4 ms 6352 KB Output is correct
102 Correct 37 ms 6480 KB Output is correct
103 Correct 5 ms 6352 KB Output is correct
104 Correct 12 ms 6352 KB Output is correct
105 Correct 3 ms 6352 KB Output is correct
106 Correct 19 ms 6480 KB Output is correct
107 Correct 20 ms 6448 KB Output is correct