站外题求助,一直TLE,求优化或新思路
查看原帖
站外题求助,一直TLE,求优化或新思路
742227
zhenghaokanzheni楼主2023/7/23 20:16
给出一个整数n,表示一共有n个集合.

接下来n行依次描述的这n个集合,每行第一个整数mi表示集合中整数的数量,接下来mi个正整数表示该集合中的各个元素.

接下来一行包含一个整数q,表示接下来有q次询问.

每个询问占一行,包含两个整数x、y,求多少个不同的整数与x处于同一集合,又和y处于同一集合的.

数据保证x和y均至少在一个集合中出现过.

1 ≤ n ≤ 50
1 ≤ mi ≤ 500
1 ≤ q ≤ 500
集合中的整数不大于10000
input           output
3		2 3 3 3 1		
3 1 2 3
4 1 3 4 5
3 2 5 6
5
1 2
1 3
2 4
1 5
5 6
#include<bits/stdc++.h>
using namespace std;
unordered_map<int,bool> mp;
int a[505];
inline int find(int a,int b)
{
    if(a<b) swap(a,b);
    return a*10000+b;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;
    while(n--)
    {
        int m;
        cin>>m;
        for(int i=1;i<=m;i++)   cin>>a[i];
        //将集合中所有位于同一集合数对存入unordered_map;
        for(int i=1;i<m;i++)
        {
            for(int j=i+1;j<=m;j++)
            {
                int k=find(a[i],a[j]);
                if(!mp.count(k)) mp[k]=true;
            }
        }
    }

    int p;
    cin>>p;
    while(p--)
    {
        int x,y,cnt;
        cin>>x>>y;
        //暴力所有可能数对,看是否存在
        for(int i=1;i<10000;i++)
        {
            if(mp.count(find(i,x))&&mp.count(find(i,y)))    cnt++;
        }
        cout<<cnt<<"\n";
    }
}

2023/7/23 20:16
加载中...