Submission #348325

#	Time	Username	Problem	Language	Result	Execution time	Memory
348325		denkendoemeer	Duathlon (APIO18_duathlon)	C++14	100 / 100	141 ms	29164 KiB

count_triplets

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int disc[100005],low[100005],st[100005],u,cnt,tn,n;
vector<int>g[100005],g2[200005];
ll sz[200005],n2,ans;
void dfs(int nod,int t)
{
    disc[nod]=low[nod]=++tn;
    st[u++]=nod;
    ++n2;
    for(auto it:g[nod])
        if (disc[it]==0){
            dfs(it,nod);
            low[nod]=min(low[nod],low[it]);
            if (low[it]>=disc[nod]){
                g2[nod].push_back(cnt+n);
                while(g2[cnt+n].empty() || g2[cnt+n].back()!=it)
                    g2[cnt+n].push_back(st[--u]);
                ++cnt;
            }
        }
        else
            if (it!=t)
                low[nod]=min(low[nod],disc[it]);
}
void dfs2(int nod,int t)
{
    if (nod<n)
        sz[nod]=1;
    else
        sz[nod]=0;
    for(auto it:g2[nod]){
        dfs2(it,nod);
        sz[nod]+=sz[it];
        if (nod>=n)
            if (t==-1)
                ans=ans-(g2[nod].size()-1)*sz[it]*(sz[it]-1);
            else
                ans=ans-g2[nod].size()*sz[it]*(sz[it]-1);
    }
    if (nod>=n)
        ans=ans-g2[nod].size()*(n2-sz[nod])*(n2-sz[nod]-1);
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int m,x,y,i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        x--;
        y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(i=0;i<n;i++){
        if (disc[i])
            continue;
        dfs(i,-1);
        ans=ans+n2*(n2-1)*(n2-2);
        dfs2(i,-1);
        n2=0;
    }
    printf("%lld\n",ans);
return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'void dfs2(int, int)':
count_triplets.cpp:36:12: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   36 |         if (nod>=n)
      |            ^
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
count_triplets.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~

• 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