Submission #977192

#	Time	Username	Problem	Language	Result	Execution time	Memory
977192		12345678	Duathlon (APIO18_duathlon)	C++17	100 / 100	76 ms	30636 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;

#define ll long long

ll n, m, u, v, sz[nx], t, in[nx], low[nx], res, cnt, idx; 
vector<ll> d[nx], b[nx];
stack<ll> s;

void tarjan(int u, int p)
{
    //printf("debug %d %d\n", u, p);
    in[u]=low[u]=++t;
    s.push(u);
    cnt++;
    for (auto v:d[u])
    {
        if (v==p) continue;
        if (!in[v]) 
        {
            tarjan(v, u), low[u]=min(low[u], low[v]);
            if (low[v]>=in[u])
            {
                idx++;
                //printf("new compoennt %d %d %d\n", idx, u, v);
                b[u].push_back(n+idx);
                while (b[n+idx].empty()||b[n+idx].back()!=v) b[n+idx].push_back(s.top()), s.pop();
            }
        }
        else low[u]=min(low[u], in[v]);
    }
    //cout<<"tarjan "<<u<<' '<<in[u]<<' '<<low[u]<<'\n';
}

void dfs(int u)
{
    //printf("dfs %d\n", u);
    sz[u]=(u<=n);
    for (auto v:b[u])
    {
        dfs(v);
        sz[u]+=sz[v];
        if (v<=n) res-=b[u].size()*(sz[v])*(sz[v]-1);
    }
    if (u>n) res-=b[u].size()*(cnt-sz[u])*(cnt-sz[u]-1);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=m; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u);
    for (int i=1; i<=n; i++) if (!in[i]) cnt=0, tarjan(i, i), res+=cnt*(cnt-1)*(cnt-2), dfs(i);
    cout<<res;
}

/*
4 3
1 2
2 3
3 4

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