Submission #235028

#	Time	Username	Problem	Language	Result	Execution time	Memory
235028		Andrei_Cotor	Duathlon (APIO18_duathlon)	C++11	100 / 100	154 ms	31864 KiB

count_triplets

//gasesc pe pc si o alta tentativa (la care nu i-am dat submit)
//biconexe...
#include<iostream>
#include<vector>
#include<algorithm>
#include<deque>

using namespace std;

vector<int> A[100005];
vector<int> CB[100005],B[100005];
int Lev[100005],Low[100005],Sz[100005];
deque<int> S;
int nrb;

void dfs(int nod, int p)
{
    S.push_back(nod);
    Lev[nod]=1+Lev[p];
    Low[nod]=Lev[nod];
    for(auto other:A[nod])
    {
        if(other==p)
            continue;

        if(!Lev[other])
        {
            dfs(other,nod);
            Low[nod]=min(Low[nod],Low[other]);

            if(Low[other]>=Lev[nod])
            {
                nrb++;
                while(1)
                {
                    int x=S.back();
                    S.pop_back();

                    B[nrb].push_back(x);
                    CB[x].push_back(nrb);

                    if(x==other)
                        break;
                }

                B[nrb].push_back(nod);
                CB[nod].push_back(nrb);
            }
        }
        else
        {
            Low[nod]=min(Low[nod],Lev[other]);
        }
    }
}

bool Viz[100005];
void getSz(int cb, int pnod)
{
    Viz[cb]=1;
    Sz[cb]=B[cb].size();

    for(auto nod:B[cb])
    {
        if(nod==pnod)
            continue;

        for(auto other:CB[nod])
        {
            if(other==cb)
                continue;

            getSz(other,nod);
            Sz[cb]+=(Sz[other]-1);
        }
    }
}

long long rez;
void solve(int cb, int root, int p, int pnod)
{
    Viz[cb]=1;
    long long sum=0;
    for(auto nod:B[cb])
    {
        //in cate moduri pot sa aleg s si f ai daca iau centrul din biconexa va trece drumul de 2 ori prin nod
        if(nod==pnod)
        {
            sum=sum+1LL*(Sz[root]-Sz[cb]+1)*(Sz[root]-Sz[cb]);
            continue;
        }

        int sz=1;
        for(auto other:CB[nod])
        {
            if(other==cb)
                continue;

            solve(other,root,cb,nod);
            sz+=(Sz[other]-1);
        }

        sum=sum+1LL*sz*(sz-1);
    }

    for(auto nod:B[cb]) //aleg punctul c in nod
    {
        if(nod==pnod)
        {
            rez-=(sum-1LL*(Sz[root]-Sz[cb]+1)*(Sz[root]-Sz[cb]));
            continue;
        }
        

        int sz=1;
        for(auto other:CB[nod])
        {
            if(other==cb)
                continue;

            sz+=(Sz[other]-1);
        }

        rez-=(sum-1LL*sz*(sz-1));
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,m;
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        cin>>x>>y;

        A[x].push_back(y);
        A[y].push_back(x);
    }

    for(int i=1; i<=n; i++)
    {
        if(!Lev[i])
            dfs(i,0);
    }

    for(int i=1; i<=nrb; i++)
    {
        if(!Viz[i])
        {
            getSz(i,0);
            rez=rez+1LL*Sz[i]*(Sz[i]-1)*(Sz[i]-2);
        }
    }

    for(int i=1; i<=nrb; i++)
        Viz[i]=0;

    for(int i=1; i<=nrb; i++)
    {
        if(!Viz[i])
            solve(i,i,0,0);
    }

    cout<<rez<<"\n";
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 15 / 15
• Subtask 7: 20 / 20
• Subtask 8: 8 / 8
• Subtask 9: 10 / 10