Submission #698833

#	Time	Username	Problem	Language	Result	Execution time	Memory
698833		Hanksburger	Duathlon (APIO18_duathlon)	C++17	100 / 100	110 ms	26808 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
long long sz[200005], tin[100005], low[100005], timer, bccs, cnt, ans, n, m;
vector<long long> bcc[200005], adj[100005];
stack<long long> s;
void dfs(long long u, long long p)
{
    cnt++;
    s.push(u);
    low[u]=tin[u]=(++timer);
    for (long long v:adj[u])
    {
        if (v==p)
            continue;
        if (tin[v])
        {
            low[u]=min(low[u], tin[v]);
            continue;
        }
        dfs(v, u);
        low[u]=min(low[u], low[v]);
        if (low[v]>=tin[u])
        {
            bcc[u].push_back(n+(++bccs));
            while (bcc[n+bccs].empty() || bcc[n+bccs].back()!=v)
            {
                bcc[n+bccs].push_back(s.top());
                s.pop();
            }
        }
    }
}
void dfs2(long long u)
{
    sz[u]=(u<=n);
    for (long long v:bcc[u])
    {
        dfs2(v);
        sz[u]+=sz[v];
        if (u>n)
            ans-=bcc[u].size()*sz[v]*(sz[v]-1);
    }
    if (u>n)
        ans-=bcc[u].size()*(cnt-sz[u])*(cnt-sz[u]-1);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (long long i=1; i<=m; i++)
    {
        long long u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (long long i=1; i<=n; i++)
    {
        if (!tin[i])
        {
            cnt=0;
            dfs(i, 0);
            ans+=cnt*(cnt-1)*(cnt-2);
            dfs2(i);
        }
    }
    cout << ans;
}

• 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