QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#404546#5707. Viruseszhaohaikun0 605ms3896kbC++202.5kb2024-05-04 07:53:512024-05-04 07:53:51

Judging History

你现在查看的是最新测评结果

  • [2024-05-04 07:53:51]
  • 评测
  • 测评结果:0
  • 用时:605ms
  • 内存:3896kb
  • [2024-05-04 07:53:51]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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%