Submission #152966

#	Time	Username	Problem	Language	Result	Execution time	Memory
152966		arnold518	Duathlon (APIO18_duathlon)	C++14	31 / 100	138 ms	22008 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int MAXM = 2e5;

int N, M;
pii edge[MAXM+10];
vector<int> adj[MAXN+10], adj2[MAXN+10];
ll ans;

int bcc[MAXN+10], bcnt=1, bsz[MAXN+10];
int idx[MAXN+10], cnt=1;
vector<int> S;
int dfs(int now, int bef)
{
    idx[now]=cnt++; S.push_back(now);
    int ret=idx[now];

    for(int nxt : adj[now])
    {
        if(nxt==bef) continue;
        if(idx[nxt]) ret=min(ret, idx[nxt]);
        else
        {
            int t=dfs(nxt, now);
            ret=min(ret, t);
            if(t>idx[now])
            {
                while(1)
                {
                    int t=S.back(); S.pop_back();
                    bcc[t]=bcnt; bsz[bcnt]++;
                    if(t==nxt) break;
                }
                bcnt++;
            }
        }
    }
    return ret;
}

int sz[MAXN+10];
bool vis[MAXN+10];

void dfs1(int now, int bef)
{
    sz[now]=bsz[now]; vis[now]=true;
    for(int nxt : adj2[now])
    {
        if(nxt==bef) continue;
        dfs1(nxt, now);
        sz[now]+=sz[nxt];
    }
}

void dfs2(int now, int bef)
{
    int sum=0;
    for(int nxt : adj2[now])
    {
        if(nxt==bef) continue;
        sz[now]-=sz[nxt];
        sz[nxt]+=sz[now];
        dfs2(nxt, now);
        sz[nxt]-=sz[now];
        sz[now]+=sz[nxt];
    }
    ll a=0, b=0, c=0;
    a+=(ll)bsz[now]*(bsz[now]-1)*(bsz[now]-2);
    for(int nxt : adj2[now])
    {
        b-=(ll)sz[nxt]*sz[nxt];
        sum+=sz[nxt];
    }
    b+=(ll)sum*sum;
    b*=bsz[now];
    c=(ll)sum*bsz[now]*(bsz[now]-1)*2-(ll)sum*(bsz[now]-1)*2;

    ans+=a+b+c;
}

int main()
{
    int i, j;

    scanf("%d%d", &N, &M);
    for(i=1; i<=M; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        edge[i]={u, v};
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(i=1; i<=N; i++) if(idx[i]==0)
    {
        dfs(i, i);
        while(1)
        {
            int t=S.back(); S.pop_back();
            bcc[t]=bcnt; bsz[bcnt]++;
            if(t==i) break;
        }
        bcnt++;
    }
    bcnt--;

    for(i=1; i<=M; i++)
    {
        int u=edge[i].first, v=edge[i].second;
        if(bcc[u]==bcc[v]) continue;
        adj2[bcc[u]].push_back(bcc[v]);
        adj2[bcc[v]].push_back(bcc[u]);
    }

    for(i=1; i<=bcnt; i++)
    {
        sort(adj2[i].begin(), adj2[i].end());
        adj2[i].erase(unique(adj2[i].begin(), adj2[i].end()), adj2[i].end());
    }

    for(i=1; i<=bcnt; i++) if(!vis[i])
    {
        dfs1(i, i);
        dfs2(i, i);
    }
    printf("%lld", ans);
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:89:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
count_triplets.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
count_triplets.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~

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