Submission #413576

#	Time	Username	Problem	Language	Result	Execution time	Memory
413576		ScarletS	Duathlon (APIO18_duathlon)	C++17	66 / 100	101 ms	22216 KiB

count_triplets

#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;

const int N = 1e5+7;
int g[N], tin[N], low[N], sub[N], t, ct, same[N], tot;
long long ans;
vector<int> e[N];
vector<array<int,2>> bccE[N];
bitset<N> d1, d2;

void dfs1(int c, int p)
{
    d1[c]=1;
    tin[c] = low[c] = ++t;
    for (int i : e[c])
        if (i!=p)
        {
            if (d1[i])
                low[c]=min(low[c],tin[i]);
            else
            {
                dfs1(i,c);
                low[c]=min(low[c],low[i]);
            }
        }
}

void dfs2(int c, int gp)
{
    ++g[gp];
    d2[c]=1;
    for (int i : e[c])
        if (!d2[i])
        {
            if (tin[c]<low[i])
            {
                bccE[gp].push_back({++ct,c});
                bccE[ct].push_back({gp,i});
                dfs2(i,ct);
            }
            else
                dfs2(i,gp);
        }
}

void dfs3(int c, int p)
{
    sub[c]=g[c];
    for (auto i : bccE[c])
        if (i[0]!=p)
        {
            dfs3(i[0],c);
            sub[c]+=sub[i[0]];
        }
}

void dfs4(int c, int p)
{
    //3
    ans+=1LL*g[c]*(g[c]-1)*(g[c]-2);
    int x=0;
    for (auto i : bccE[c])
    {
        if (i[0]!=p)
        {
            dfs4(i[0],c);
            //2 1
            ans+=2LL*sub[i[0]]*(g[c]-1)*(g[c]-1);
            //1 1 1
            ans+=2LL*sub[i[0]]*same[i[1]];
            ans+=2LL*g[c]*sub[i[0]]*(x-same[i[1]]);
            
            same[i[1]]+=sub[i[0]];
            x+=sub[i[0]];
        }
        else
        {
            //2 1
            ans+=2LL*(tot-sub[c])*(g[c]-1)*(g[c]-1);
            //1 1 1
            ans+=2LL*(tot-sub[c])*same[i[1]];
            ans+=2LL*g[c]*(tot-sub[c])*(x-same[i[1]]);

            same[i[1]]+=(tot-sub[c]);
            x+=(tot-sub[c]);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,m,x,y;
    cin>>n>>m;
    while (m--)
    {
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    for (int i=1;i<=n;++i)
        if (!d1[i])
        {
            dfs1(i,0);
            dfs2(i,++ct);
            dfs3(ct,0);
            tot=sub[ct];
            dfs4(ct,0);
        }
    cout<<ans;
    return 0;
}

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