Unrequited Love
Time Limit: 16 Seconds Memory Limit: 131072 KB
There are n single boys and m single girls. Each of them may love none, one or several of other people unrequitedly and one-sidedly. For the coming q days, each night some of them will come together to hold a single party. In the party, if someone loves all the others, but is not loved by anyone, then he/she is called king/queen of unrequited love.
Input
There are multiple test cases. The first line of the input is an integer T ≈ 50 indicating the number of test cases.
Each test case starts with three positive integers no more than 30000
-- n m q
. Then each of the next n lines describes a boy, and each of the next m lines describes a girl. Each line consists of the name, the number of unrequitedly loved people, and the list of these people's names. Each of the last q lines describes a single party. It consists of the number of people who attend this party and their names. All people have different names whose lengths are no more than 20
. But there are no restrictions that all of them are heterosexuals.
Output
For each query, print the number of kings/queens of unrequited love, followed by their names in lexicographical order, separated by a space. Print an empty line after each test case. See sample for more details.
Sample Input
2
2 1 4
BoyA 1 GirlC
BoyB 1 GirlC
GirlC 1 BoyA
2 BoyA BoyB
2 BoyA GirlC
2 BoyB GirlC
3 BoyA BoyB GirlC
2 2 2
H 2 O S
He 0
O 1 H
S 1 H
3 H O S
4 H He O S
Sample Output
0
0
1 BoyB
0 0
0 看的人家的代码算是理解了,我是直接比较的明显要超时(n^2),换个思路后时间复杂度变为(2*n)代码:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<map>
#include<set>
using namespace std;
char s1[],s2[],s3[];
int main()
{
int T;
int n,m,q,n0;
scanf("%d",&T);
while(T--)
{
string lovy,lovyed;
map< pair<string,string> ,int >love;
love.clear();
scanf("%d %d %d",&n,&m,&q);
lovy = lovyed = "";
while(n--)
{
scanf("%s %d",s1,&n0);
lovy = s1;
while(n0--)
{
scanf("%s",s2);
lovyed = s2;
love[make_pair(lovy,lovyed)] = ;
}
lovy = lovyed = "";
} while(m--)
{
scanf("%s %d",s1,&n0);
lovy = s1;
while(n0--)
{
scanf("%s",s2);
lovyed = s2;
love[make_pair(lovy,lovyed)] = ;
}
lovy = lovyed = "";
}
while(q--)
{ bool flag = true;
int k =;
string mm[];
scanf("%d",&n0);
scanf("%s",s1);
mm[]=lovy = s1;
for(int i=;i<n0;i++)
{
scanf("%s",s1);
lovyed = mm[i] = s1;
//关键在于下面的判断
if(love[make_pair(lovy,lovyed)] == || love[make_pair(lovyed,lovy)] == )
{
lovy = mm[i];
k = i;
}
}
for(int j=;j<k;j++)
{
if(lovy != mm[j])
{
if(love[make_pair(lovy,mm[j])] == || love[make_pair(mm[j],lovy)] == )
{
flag = false;
}
}
}
if(flag)
printf("1 %s\n",lovy.c_str());
else printf("0\n");
}
printf("\n");
}
return ;
}