Facebook Hacker Cup 2020 Round 1 C

C.cpp

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <utility>
#include <functional>
#include <algorithm>
using namespace std;

int main()
{
    int T;
    cin>>T;
    for (int t=1; t<=T; t++)
    {
        int N, K;
        cin>>N>>K;
        string S;
        cin>>S;
        vector<int> E(N+1);
        for (int i=2; i<=K+1; i++)
            cin>>E[i];
        {
            long long A, B, C;
            cin>>A>>B>>C;
            for (int i=K+2; i<=N; i++)
                E[i] = (int)(((A*E[i-2]+B*E[i-1]+C)%(i-1))+1);
        }

        vector<vector<int>> EE(N);
        for (int i=2; i<=N; i++)
        {
            EE[i-1].push_back(E[i]-1);
            EE[E[i]-1].push_back(i-1);
        }

        //  最大の連結成分のサイズ
        map<pair<int, int>, int> M;
        //  最大の連結成分の個数
        map<pair<int, int>, int> MN;
        //  頂点数
        map<pair<int, int>, int> C1;
        //  親に連結している頂点数
        map<pair<int, int>, int> C2;
        //  互いに行き来できる部屋の組数
        map<pair<int, int>, long long> A;

        function<void(int, int)> f1 = [&](int c, int p)
        {
            A[{c, p}] = 0;
            M[{c, p}] = -1;
            MN[{c, p}] = 0;
            C1[{c, p}] = 0;
            C2[{c, p}] = 0;

            for (int e: EE[c])
                if (e!=p)
                {
                    f1(e, c);

                    if (M[{e, c}]>M[{c, p}])
                    {
                        M[{c, p}] = M[{e, c}];
                        MN[{c, p}] = 0;
                    }
                    if (M[{e, c}]==M[{c, p}])
                        MN[{c, p}] += MN[{e, c}];

                    C1[{c, p}] += C1[{e, c}];
                    C2[{c, p}] += C2[{e, c}];

                    A[{c, p}] += A[{e, c}];
                    if (S[c]=='*')
                        A[{c, p}] -= C2[{e, c}]*(C2[{e, c}]-1)/2;
                }

            C1[{c, p}]++;
            if (S[c]=='*')
                C2[{c, p}]++;
            else
                C2[{c, p}] = 0;

            if (C2[{c, p}]>M[{c, p}])
            {
                M[{c, p}] = C2[{c, p}];
                MN[{c, p}] = 0;
            }
            if (C2[{c, p}]==M[{c, p}])
                MN[{c, p}]++;

            A[{c, p}] += C2[{c, p}]*(C2[{c, p}]-1)/2;
        };
        f1(0, -1);

        function<void(int, int)> f2 = [&](int c, int p)
        {
            int n = (int)EE[c].size();
            vector<int> ML(n, -1), MR(n, -1);
            vector<int> MNL(n), MNR(n);

            for (int i=0; i<n-1; i++)
            {
                int e = EE[c][i];
                if (M[{e, c}]>ML[i])
                {
                    ML[i+1] = M[{e, c}];
                    MNL[i+1] = 0;
                }
                else
                {
                    ML[i+1] = ML[i];
                    MNL[i+1] = MNL[i];
                }
                if (M[{e, c}]==ML[i+1])
                    MNL[i+1] += MN[{e, c}];
            }

            for (int i=n-1; i>0; i--)
            {
                int e = EE[c][i];
                if (M[{e, c}]>MR[i])
                {
                    MR[i-1] = M[{e, c}];
                    MNR[i-1] = 0;
                }
                else
                {
                    MR[i-1] = MR[i];
                    MNR[i-1] = MNR[i];
                }
                if (M[{e, c}]==MR[i-1])
                    MNR[i-1] += MN[{e, c}];
            }

            int c1s = 0;
            int c2s = 0;
            for (int e: EE[c])
            {
                c1s += C1[{e, c}];
                c2s += C2[{e, c}];
            }

            long long as = 0;
            for (int e: EE[c])
            {
                as += A[{e, c}];
                if (S[c]=='*')
                    as -= C2[{e, c}]*(C2[{e, c}]-1)/2;
            }

            for (int i=0; i<n; i++)
            {
                int e = EE[c][i];
                int m = ML[i];
                int mn = MNL[i];
                if (MR[i]>m)
                {
                    m = MR[i];
                    mn = 0;
                }
                if (MR[i]==m)
                    mn += MNR[i];

                int c1 = c1s - C1[{e, c}];
                int c2 = c2s - C2[{e, c}];
                c1++;
                if (S[c]=='*')
                    c2++;
                else
                    c2 = 0;

                if (c2>m)
                {
                    m = c2;
                    mn = 0;
                }
                if (c2==m)
                    mn++;

                long long a = as - A[{e, c}];
                if (S[c]=='*')
                    a += C2[{e, c}]*(C2[{e, c}]-1)/2;
                a += c2*(c2-1)/2;

                M[{c, e}] = m;
                MN[{c, e}] = mn;
                C1[{c, e}] = c1;
                C2[{c, e}] = c2;
                A[{c, e}] = a;
            }

            for (int e: EE[c])
                if (e!=p)
                    f2(e, c);
        };
        f2(0, -1);

        long long ans = -1;
        long long ansn = 0;
        for (int i=0; i<N; i++)
            for (int e: EE[i])
                if (i<e)
                {
                    long long m = M[{i, e}]+M[{e, i}];
                    long long a = 0;
                    a += A[{i, e}] - M[{i, e}]*(M[{i, e}]-1)/2;
                    a += A[{e, i}] - M[{e, i}]*(M[{e, i}]-1)/2;
                    a += m*(m-1)/2;

                    if (a>ans)
                    {
                        ans = a;
                        ansn = 0;
                    }
                    if (a==ans)
                    {
                        if (M[{i, e}]==0 || M[{e, i}]==0)
                            ansn += (long long)C1[{i, e}]*C1[{e, i}];
                        else
                            ansn += (long long)M[{i, e}]*MN[{i, e}]*M[{e, i}]*MN[{e, i}];
                    }
                }

        cout<<"Case #"<<t<<": "<<ans<<" "<<ansn<<endl;
    }
}