Submission #689374

#	Time	Username	Problem	Language	Result	Execution time	Memory
689374		ToroTN	Duathlon (APIO18_duathlon)	C++14	100 / 100	121 ms	27528 KiB

count_triplets

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
ll n,m,u_i,v_i,dis[100005],low[100005],cnt,bcc=0,ans=0,num,sz[200005];
vector<ll> v[100005],g[200005];
stack<ll> stk;
void dfs(ll u,ll p)
{
    dis[u]=low[u]=++cnt;
    ++num;
    stk.push(u);
    for(auto node:v[u])
    {
        if(node==p)continue;
        if(dis[node]!=0)
        {
            low[u]=min(low[u],dis[node]);
        }else
        {
            dfs(node,u);
            low[u]=min(low[u],low[node]);
            if(dis[u]<=low[node])
            {
                ++bcc;
                //printf("node=%d\n",node);
                g[u].pb(n+bcc);
                while(!g[n+bcc].size()||g[n+bcc].back()!=node)
                {
                    g[n+bcc].pb(stk.top());
                    stk.pop();
                }
            }
        }
    }
}
void dfs2(ll u)
{
    sz[u] = (u<=n) ;
    for(auto node:g[u])
    {
        dfs2(node);
        sz[u]+=sz[node];
        if(u>n)ans-=(g[u].size()*sz[node]*(sz[node]-1));
        //printf("%lld %lld %lld\n",u,node,ans);
        //printf("%lld %lld\n",g[u].size(),sz[node]);
        //printf("%lld\n",g[u].size()*sz[node]*(sz[node]-1));
    }
    if(u>n)ans-=(g[u].size()*(num-sz[u])*(num-sz[u]-1));
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&u_i,&v_i);
        v[u_i].pb(v_i);
        v[v_i].pb(u_i);
    }
    for(int i=1;i<=n;i++)
    {
        if(dis[i]==0)
        {
            num=0;
            dfs(i,0);
            ans+=num*(num-1)*(num-2);
            //printf("%lld\n",ans);
            dfs2(i);
            //printf("%lld\n\n",ans);
        }
    }
    /*for(int i=1;i<=8;i++)
    {
        printf("i=%d\n",i);
        for(auto node:g[i])
        {
            printf("%lld ",node);
        }
        printf("\n");
    }*/
    /*for(int i=1;i<=8;i++)
    {
        printf("%lld ",sz[i]);
    }
    printf("\n");
    for(int i=1;i<=8;i++)
    {
        printf("%lld ",g[i].size());
    }
    printf("\n");*/
    printf("%lld\n",ans);
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf("%lld%lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
count_triplets.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%lld%lld",&u_i,&v_i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• 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