Submission #166740

#	Time	Username	Problem	Language	Result	Execution time	Memory
166740		combi1k1	Duathlon (APIO18_duathlon)	C++14	100 / 100	321 ms	29016 KiB

count_triplets

#include<bits/stdc++.h>

using namespace std;

const int   N   = 1e5 + 1;

vector<int> g[N];
vector<int> a[N + N];

void addEdge(int u,int v)   {
    a[u].push_back(v);
    a[v].push_back(u);
    //cerr << u << " " << v << "\n";
}

int dfn[N], low[N];
int nCh[N + N];
int tot, siz;
int ver = N;

long long ans = 0;

stack<int>  st;

void dfs(int u,int p)   {
    siz++;
    tot++;
    dfn[u] = tot;
    low[u] = tot;

    st.push(u);

    for(int v : g[u])   if (v != p) {
        if (dfn[v])     low[u] = min(low[u],dfn[v]);
        if(!dfn[v]) {
            dfs(v,u);   low[u] = min(low[u],low[v]);
            if (low[v] >= dfn[u])   {
                ver++;  addEdge(u,ver);
                int z;
                do  {
                    z = st.top();   st.pop();
                    addEdge(z,ver);
                }   while (z != v);
            }
        }
    }
}
void cal(int u,int p)   {
    if (u < N)
        nCh[u] = 1;

    for(int v : a[u])   if (v != p) {
        cal(v,u);
        nCh[u] += nCh[v];
    }
    if (u < N)  return;

    for(int v : a[u])   {
        int T_T;
        if (v != p) T_T = nCh[v];
        else        T_T = siz - nCh[u];

        ans -= 1ll * T_T * (T_T - 1) * (a[u].size() - 1);
    }
}

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

    int n;  cin >> n;
    int m;  cin >> m;

    for(int i = 0 ; i < m ; ++i)    {
        int x;  cin >> x;
        int y;  cin >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i = 1 ; i <= n ; ++i)   if(!dfn[i]) {
        siz = 0;
        dfs(i,0);   ans += 1ll * siz * (siz - 1) * (siz - 2);
        cal(i,0);
    }

    cout << ans << endl;
}
/*
4 4
1 2
2 3
3 4
4 2
*/

• 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