Submission #656869

#	Time	Username	Problem	Language	Result	Execution time	Memory
656869		benjaminkleyn	Duathlon (APIO18_duathlon)	C++17	100 / 100	161 ms	27712 KiB

count_triplets

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

const int max_n = 100001;

int n, m;
vector<int> g[max_n];
bool vis[max_n] = {false};
int ti[max_n] = {0}, lo[max_n], timer = 0;

ll N;
ll sz[2 * max_n];
ll ans = 0;

vector<int> G[2 * max_n];
int bcc_cnt = 1;

stack<int> s;
void dfs1(int u, int p = -1)
{
    vis[u] = true;
    ti[u] = lo[u] = timer++;
    N++;
    s.push(u);
    for (int v : g[u])
        if (v != p)
        {
            if (vis[v])
                lo[u] = min(lo[u], ti[v]);
            else
            {
                dfs1(v, u);
                lo[u] = min(lo[u], lo[v]);

                // if u is a cutpoint, or u is the root node
                if (lo[v] >= ti[u])
                {
                    G[u].push_back(n + bcc_cnt);
                    do
                    {
                        G[n + bcc_cnt].push_back(s.top());
                        s.pop();
                    } while (G[n + bcc_cnt].back() != v);
                    bcc_cnt++;
                }
            }
        }
}

ll dfs2(int u)
{
    // count only nodes that were in original graph,
    // not representative nodes of biconnected components.
    sz[u] = (u <= n);
    for (int v : G[u])
    {
        sz[u] += dfs2(v);
        // (if u is a representative node of a bcc)
        if (u > n)
            ans -= G[u].size() * sz[v] * (sz[v] - 1);
        // G[u].size() = the number of nodes in this bcc.
        // sz[v] = the number of nodes in subtree of v in bcc-graph.
    }
    // same as above, but considering everything that is not in the subtree of u.
    if (u > n)
        ans -= G[u].size() * (N - sz[u]) * (N - sz[u] - 1);

    return sz[u];
}

int main()
{
    cin >> n >> m;
    for (int i = 0, a, b; i < m; i++)
    {
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    for (int i = 1; i <= n; i++)
        if (!vis[i])
        {
            N = 0;
            dfs1(i);
            ans += N * (N - 1) * (N - 2);
            dfs2(i);
        }

    cout << ans << '\n';

    return 0;
}

• 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