QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#639683#6785. What Kind of Friends Are You?E_REMALWA 0ms13364kbC++141.4kb2024-10-13 21:31:202024-10-13 21:31:20

Judging History

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

  • [2024-10-13 21:31:20]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:13364kb
  • [2024-10-13 21:31:20]
  • 提交

answer

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=5e5;
int t,n,m,c,q;
string name[205];
int ans[205][30];
int ask[205][30];
string s;
int _find[205];//记录每个动物的回答能否指向唯一动物
int trie[maxn+5][5],cnt;
map <string , int> mp;
void _insert() {
	for(int i=1;i<=c;i++) {
		int p=0;
		for(int j=1;j<=m;j++) {
			if(trie[p][ans[i][j]]==-1) {
				cnt++;
				trie[p][ans[i][j]]=cnt;
			}
			p=trie[p][ans[i][j]];
		}
		if(trie[p][2]>0) trie[p][2]=-2;
		if(trie[p][2]==-1) trie[p][2]=i;
	}
}
void _search() {
	for(int i=1;i<=n;i++) {
		int p=0;
		for(int j=1;j<=m;j++) {
			p=trie[p][ask[i][j]];
		}
		//cout<<trie[p][2]<<"**"<<p<<endl;
		if(trie[p][2]<0) cout<<"Let's go to the library!!"<<endl;
		else cout<<name[trie[p][2]]<<endl;
	}
}
int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>t;
	while(t--) {
		cin>>n>>m;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++) ans[i][j]=0;
		for(int i=0;i<=maxn+1;i++) {
			trie[i][0]=-1;
			trie[i][1]=-1;
			trie[i][2]=-1;
		}
		cnt=0;
		cin>>c;
		for(int i=1;i<=c;i++) {
			cin>>name[i];
			mp[name[i]]=i;
		}
		for(int i=1;i<=m;i++) {
			cin>>q;
			for(int j=1;j<=q;j++) {
				cin>>s;
				ans[mp[s]][i]=1;
			}
		}
		_insert();//构建字典树 
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=m;j++) {
				cin>>ask[i][j];
			}
		}
		_search();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 13364kb

input:

2
3 4
5 Serval Raccoon Fennec Alpaca Moose
4 Serval Raccoon Alpaca Moose
1 Serval
1 Fennec
1 Serval
1 1 0 1
0 0 0 0
1 0 0 0
5 5
11 A B C D E F G H I J K
3 A B K
4 A B D E
5 A B K D E
10 A B K D E F G H I J
4 B D E K
0 0 1 1 1
1 0 1 0 1
1 1 1 1 1
0 0 1 0 1
1 0 1 1 1

output:

Serval
Let's go to the library!!
Let's go to the library!!

K
B
Let's go to the library!!
K

result:

wrong answer 4th lines differ - expected: 'Let's go to the library!!', found: ''