Submission #62550671

---

Source Code Expand

    #include <bits/stdc++.h>
    #pragma GCC optimize ("O3")
    #define Fast1 ios_base::sync_with_stdio(false)
    #define Fast2 cin.tie(NULL)
    #define ll long long int
    #define ull unsigned long long int
    #define ld long double
    #define pb push_back
    #define all(x) x.begin(), x.end()
    #define inf 1000000000000000000
    using namespace std;
    const int N = 100000+7;
    const ll mod = 998244353;
    string S = "abcdefghijklmnopqrstuvwxyz";
    ll lcm(ll a, ll b){ return (a*b/__gcd(a,b)); }


    // PBDS - Ordered Set  -----------------------------------------------------------------------------
    #include<ext/pb_ds/assoc_container.hpp>
    #include<ext/pb_ds/tree_policy.hpp>
    using namespace __gnu_pbds;
    template <typename T>
    using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
    //--------------------------------------------------------------------------------------------------


    // Seive, Prime Factors,Divisors ----------------------------------------------------------------------------
    bool isPrime[N+1];
    ll lowestPrime[N+1], highestPrime[N+1];
    map<ll,ll> primeFactors;
    vector<ll> divisors[100007];
    void Seive(){ memset(isPrime, 1, sizeof isPrime); memset(lowestPrime, 0, sizeof lowestPrime); memset(highestPrime, 0, sizeof highestPrime);
    isPrime[0] = isPrime[1] = 0; for(ll i=2;i<=N;i++){ if(isPrime[i]){ lowestPrime[i] = highestPrime[i] = i; for(ll j=2*i;j<=N;j+=i){
    isPrime[j] = false; highestPrime[j] = i; if(lowestPrime[j] == 0) lowestPrime[j] = i;}}}}

    void getPrimeFactors(ll num){ while(num > 1){ ll primeFactor = highestPrime[num]; while(num % primeFactor == 0){ num /= primeFactor; primeFactors[primeFactor]++;}}}

    void getDivisors(){for(ll i=2;i<=100007;i++){for(ll j=i;j<=100007;j+=i){divisors[j].pb(i);}}}
    // -------------------------------------------------------------------------------------------------



    /*----------------------------Notes----------------------------------------------------//

    1. All the perfect square numbers have odd number of divisors and 
    rest all numbers always have even number of divisors.
    2. The sum of two numbers is INT_MAX if their xor is also INT_MAX.
    3. For a number d to be divisor of any other number p, d <= floor(p)
    4. given a number y >= 2*x, the x^y val will always be greater than x,
    as there will be an extra set bit in y >= 2*x.


    */


    class DisjointSetUnion{
    public:
        vector<ll> parent, size;
        ll components;
        DisjointSetUnion(ll n){
            parent.resize(n+1);
            iota(all(parent), 0);
            size.assign(n+1, 1);
            components = n;
        }
        ll findParent(ll x){
            if(parent[x] == x) return x;
            return parent[x] = findParent(parent[x]);
        }
        void unite(ll x, ll y){
            x = findParent(x);
            y = findParent(y);
            if(x == y) return;
            if(size[x] < size[y]) swap(x,y);
            parent[y] = x;
            size[x] += size[y];
            components--;
        }

    };




void solve(){
    // freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
    ll n; cin >> n;
    vector<map<ll,ll>> num_freq(n+1);
    vector<ll> sizes(n+1);
    for(int i=1;i<=n;i++){
        ll k; cin >> k;
        sizes[i] = k;
        map<ll,ll> mp;
        for(int j=0;j<k;j++){
            ll x; cin >> x;
            mp[x]++;
        }
        num_freq[i] = mp;
    }
    // for(int i=1;i<=n;i++){
    //     for(auto it : num_freq[i]){
    //         cout << it.first<< " " << it.second << endl;
    //     }
    // }
    ld ans = 0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            auto &mp1 = num_freq[i];
            auto &mp2 = num_freq[j];
            // for(auto it : mp1){
            //     cout << it.first << " " << it.second << endl;
            // }
            // cout << endl;
            // for(auto it : mp2){
            //     cout << it.first << " " << it.second << endl;
            // }
            // cout << endl;
            ll totalPoss = sizes[i] * sizes[j];
            // cout << totalPoss << endl;
            ll favourableOut = 0;
            if(mp1.size() <= mp2.size()){
                for(auto f : mp1){
                    if(mp2.find(f.first) != mp2.end()){
                        favourableOut += f.second * mp2[f.first];
                    }
                }
            }
            else{
                for(auto f : mp2){
                    if(mp1.find(f.first) != mp1.end()){
                        favourableOut += f.second * mp1[f.first];
                    }
                }
            }
            // cout << favourableOut << endl;
            // cout << setprecision(18) << (ld)favourableOut/totalPoss << endl;
            ans = max(ans, (ld)(1.0*favourableOut/totalPoss));
        }
    }
    cout << setprecision(15) << ans << endl;
}




    int main(){     
        Fast1;
        Fast2;
        // #ifndef ONLINE_JUDGE   
        //     freopen("input.txt", "r", stdin);   
        //     freopen("output.txt", "w", stdout);   
        // #endif  
        // Seive();
        // int t;
        // cin >> t;
        // for(int i =1;i<=t;i++){
        //     // cout << "Case #" << i << ": " ;
        //     solve(); 
        // }
     
        solve();
        return 0;
    }

Submission Info

Judge Result