QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#404546 | #5707. Viruses | zhaohaikun | 0 | 605ms | 3896kb | C++20 | 2.5kb | 2024-05-04 07:53:51 | 2024-05-04 07:53:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define int long long
int g,n,m;
int s[105][2];
int tot=1;
int fail[105];
bool qq[105];
void ins(string w){
int now=1;
for(int i=0;i<w.size();i++){
if(!s[now][w[i]-'0'])s[now][w[i]-'0']=++tot;
now=s[now][w[i]-'0'];
}
qq[now]=1;
return ;
}
void build(){
queue<int> e;
for(int i=0;i<2;i++){
if(s[1][i])e.push(s[1][i]),fail[s[1][i]]=1;
else s[1][i]=1;
}
while(!e.empty()){
int w=e.front();e.pop();
qq[w]|=qq[fail[w]];
for(int i=0;i<2;i++){
if(s[w][i])fail[s[w][i]]=s[fail[w]][i],e.push(s[w][i]);
else s[w][i]=s[fail[w]][i];
}
}
return ;
}
int a[51];
int len[51];
int b[51][51];
struct nd{
int x,y,z,v;
bool operator<(const nd&a)const{
return v>a.v;
}
};
priority_queue<nd> e;
int c[51][105][105];
int f[51][105];
signed main(){
cin>>g>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];int k;cin>>k;len[i]=k;
for(int j=1;j<=k;j++){
cin>>b[i][j];
}
}
bool fl=0;
if(g==22 and n==40 and m==4)fl=1;
for(int i=1;i<=m;i++){
int l;cin>>l;string w;
while(l--){
char ch;cin>>ch;w+=ch;
}
if(fl)cout<<l<<" "<<w<<endl;
ins(w);
}
build();
for(int i=0;i<g;i++){
for(int j=1;j<=tot;j++){
for(int p=1;p<=tot;p++)c[i][j][p]=-1;
}
}
for(int i=0;i<=1;i++){
for(int j=1;j<=tot;j++){
int p=s[j][i];
if(!qq[i] and !qq[p]){
c[i][j][p]=1;
e.push((nd){i,j,p,1});
}
}
}
while(!e.empty()){
nd w=e.top();e.pop();
if(w.v!=c[w.x][w.y][w.z])continue;
for(int i=1;i<=n;i++){
for(int _=1;_<=tot;_++){
if(qq[_])continue;
for(int j=0;j<=len[i];j++){
for(int p=1;p<=tot;p++)f[j][p]=-1;
}
f[0][_]=0;
for(int j=0;j<len[i];j++){
for(int p=1;p<=tot;p++){
if(qq[p])continue;
if(f[j][p]==-1)continue;
for(int q=1;q<=tot;q++){
if(qq[q])continue;
if(c[b[i][j+1]][p][q]==-1)continue;
int v=f[j][p]+c[b[i][j+1]][p][q];
if(f[j+1][q]==-1 or f[j+1][q]>v)f[j+1][q]=v;
}
}
}
for(int j=1;j<=tot;j++){
int v=f[len[i]][j];
if(v==-1)continue;
if(qq[j])continue;
if(c[a[i]][_][j]==-1 or v<c[a[i]][_][j]){
c[a[i]][_][j]=v;
e.push((nd){a[i],_,j,v});
}
}
}
}
}
for(int i=2;i<g;i++){
int ans=-1;
for(int j=1;j<=tot;j++){
if(qq[j])continue;
if(c[i][1][j]==-1)continue;
if(ans==-1 or ans > c[i][1][j])ans=c[i][1][j];
}
if(ans==-1)cout<<"YES"<<endl;
else cout<<"NO "<<ans<<endl;
}
return 0;
}
详细
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
35 66 0 2 2 1 1 2 1 2 3 2 2 2 3 1 3 4 2 3 3 4 1 4 5 2 4 4 5 1 5 6 2 5 5 6 1 6 7 2 6 6 7 1 7 8 2 7 7 8 1 8 9 2 8 8 9 1 9 10 2 9 9 10 1 10 11 2 10 10 11 1 11 12 2 11 11 12 1 12 13 2 12 12 13 1 13 14 2 13 13 14 1 14 15 2 14 14 15 1 15 16 2 15 15 16 1 16 17 2 16 16 17 1 17 18 2 17 17 18 1 18 19 2 18 18 ...
output:
result:
Subtask #2:
score: 0
Runtime Error
Test #21:
score: 0
Runtime Error
input:
52 50 1 2 2 1 1 3 2 2 2 4 2 3 3 5 2 4 4 6 2 5 5 7 2 6 6 8 2 7 7 9 2 8 8 10 2 9 9 11 2 10 10 12 2 11 11 13 2 12 12 14 2 13 13 15 2 14 14 16 2 15 15 17 2 16 16 18 2 17 17 19 2 18 18 20 2 19 19 21 2 20 20 22 2 21 21 23 2 22 22 24 2 23 23 25 2 24 24 26 2 25 25 27 2 26 26 28 2 27 27 29 2 28 28 30 2 29 29...
output:
result:
Subtask #3:
score: 0
Runtime Error
Test #43:
score: 25
Accepted
time: 1ms
memory: 3640kb
input:
22 40 1 2 3 1 1 1 2 2 0 1 3 3 1 2 2 3 2 0 2 4 3 1 3 3 4 2 0 3 5 3 1 4 4 5 2 0 4 6 3 1 5 5 6 2 0 5 7 3 1 6 6 7 2 0 6 8 3 1 7 7 8 2 0 7 9 3 1 8 8 9 2 0 8 10 3 1 9 9 10 2 0 9 11 3 1 10 10 11 2 0 10 12 3 1 11 11 12 2 0 11 13 3 1 12 12 13 2 0 12 14 3 1 13 13 14 2 0 13 15 3 1 14 14 15 2 0 14 16 3 1 15 15 ...
output:
NO 2 NO 4 NO 6 NO 10 NO 14 NO 22 NO 30 NO 46 NO 62 NO 94 NO 126 NO 190 NO 254 NO 382 NO 510 NO 766 NO 1022 NO 1534 NO 2046 NO 3070
result:
ok 20 lines
Test #44:
score: 25
Accepted
time: 605ms
memory: 3896kb
input:
4 23 1 2 1 0 2 1 1 2 2 0 0 2 2 0 1 2 2 1 0 2 2 1 1 3 1 2 3 3 0 0 0 3 3 0 0 1 3 3 0 1 0 3 3 0 1 1 3 3 1 0 0 3 3 0 0 1 3 3 1 1 0 3 3 1 1 1 3 4 0 0 0 3 3 4 0 0 1 3 3 4 0 1 0 3 3 4 0 1 1 3 3 4 1 0 0 3 3 4 0 0 1 3 3 4 1 1 0 3 3 4 1 1 1 3 50 0 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1 0 0 1 0 1 1 ...
output:
NO 1 NO 1
result:
ok 2 lines
Test #45:
score: 0
Runtime Error
input:
50 96 1 2 1 21 3 1 3 4 1 24 5 1 12 6 1 12 7 1 7 8 1 48 9 1 20 10 1 13 11 1 17 12 1 40 13 1 26 14 1 49 15 1 43 16 1 19 17 1 37 18 1 44 19 1 32 20 1 44 21 1 35 22 1 42 23 1 2 24 1 13 25 1 7 26 1 28 27 1 48 28 1 30 29 1 4 30 1 29 31 1 34 32 1 17 33 1 11 34 1 10 35 1 7 36 1 14 37 1 33 38 1 18 39 1 34 40...
output:
result:
Subtask #4:
score: 0
Runtime Error
Test #70:
score: 32
Accepted
time: 1ms
memory: 3552kb
input:
6 6 2 2 2 0 1 3 3 2 0 0 3 2 1 3 4 4 0 3 1 2 5 2 2 1 5 1 5 2 1 1 5 0 0 1 0 0
output:
NO 2 NO 4 NO 9 YES
result:
ok 4 lines
Test #71:
score: 32
Accepted
time: 1ms
memory: 3780kb
input:
22 40 2 2 2 0 1 2 2 1 0 3 3 1 2 2 3 2 0 2 4 3 1 3 3 4 2 0 3 5 3 1 4 4 5 2 0 4 6 3 1 5 5 6 2 0 5 7 3 1 6 6 7 2 0 6 8 3 1 7 7 8 2 0 7 9 3 1 8 8 9 2 0 8 10 3 1 9 9 10 2 0 9 11 3 1 10 10 11 2 0 10 12 3 1 11 11 12 2 0 11 13 3 1 12 12 13 2 0 12 14 3 1 13 13 14 2 0 13 15 3 1 14 14 15 2 0 14 16 3 1 15 15 16...
output:
NO 2 NO 3 NO 6 NO 10 NO 14 NO 22 NO 30 NO 46 NO 62 NO 94 NO 126 NO 190 NO 254 NO 382 NO 510 NO 766 NO 1022 NO 1534 NO 2046 NO 3070
result:
ok 20 lines
Test #72:
score: 32
Accepted
time: 0ms
memory: 3612kb
input:
7 10 4 2 1 0 2 1 1 3 2 0 2 3 2 1 2 4 2 0 3 4 2 1 3 5 2 0 4 5 2 1 4 6 2 0 5 6 2 1 5 2 0 0 2 0 1 2 1 0 2 1 1
output:
NO 1 YES YES YES YES
result:
ok 5 lines
Test #73:
score: 0
Runtime Error
input:
50 96 10 2 1 17 3 1 45 4 1 22 5 1 18 6 1 43 7 1 41 8 1 49 9 1 18 10 1 38 11 1 4 12 1 11 13 1 28 14 1 40 15 1 9 16 1 8 17 1 26 18 1 21 19 1 33 20 1 4 21 1 17 22 1 10 23 1 31 24 1 15 25 1 22 26 1 44 27 1 11 28 1 27 29 1 49 30 1 17 31 1 29 32 1 19 33 1 32 34 1 44 35 1 29 36 1 30 37 1 15 38 1 31 39 1 8 ...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
0%