// ~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';
}
}
Compilation message
Viruses.cpp:170:1: error: extended character is not valid in an identifier
170 |
| ^
Viruses.cpp:170:1: error: '\U000000a0' does not name a type
170 |
| ^
