Submission #578936

#	Time	Username	Problem	Language	Result	Execution time	Memory
578936		noedit	Duathlon (APIO18_duathlon)	C++17	100 / 100	261 ms	40768 KiB

count_triplets

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
#define sz(x) (x.size())
using namespace std;
using namespace __gnu_pbds;

template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
//#define int long long

const int MAXN = 1e5, MAXM = 2e5, MAXK = 3e5;
int timer = 0, n, m, all = 0;
int tin[MAXN], up[MAXN], sz[MAXK];
vector<int> gr[MAXK], arr;
vector<pair<int, int> > g[MAXN], gt[MAXN];
bool used[MAXK], was[MAXM], vis[MAXN];
deque<int> q;
ll ans = 0;

void dfs0(int v, int p)
{
    used[v] = 1;
    tin[v] = up[v] = timer++;
    for (auto& [u, id] : g[v])
    {
        if (u == p) {continue;}
        if (used[u])
        {
            up[v] = min(up[v], tin[u]);
            if (tin[u] < tin[v])
            {
                gt[v].push_back({u, id});
            }
        }
        else
        {
            if (p == -1)
            {
                q.push_back(id);
                was[id] = 1;
            }
            dfs0(u, v);
            gt[v].push_back({u, id});
            up[v] = min(up[v], up[u]);
        }
    }
}

void dfs1(int v)
{
    if (vis[v])
    {
        return;
    }
    vis[v] = 1;
    for (auto& [u, id] : gt[v])
    {
        if (was[id])
        {
            continue;
        }
        was[id] = 1;
        if (up[u] < tin[v])
        {
            arr.push_back(id);
            dfs1(u);
        }
        else
        {
            q.push_back(id);
        }
    }
}

void dfs2(int v, int p)
{
    used[v] = 1;
    if (v < n)
    {
        sz[v] = 1;
    }
    for (auto& u : gr[v])
    {
        if (u != p)
        {
            dfs2(u, v);
            sz[v] += sz[u];
        }
    }
}

void dfs3(int v, int p)
{
    int cur = all - sz[v];
    if (v >= n)
    {
        int k = gr[v].size();
        ans -= cur * 1ll * (cur - 1) * (k - 1);
        for (auto& u : gr[v])
        {
            if (u != p)
            {
                ans -= sz[u] * 1ll * (sz[u] - 1) * (k - 1);
            }
        }
    }
    for (auto& u : gr[v])
    {
        if (u != p)
        {
            dfs3(u, v);
        }
    }
}

void solve()
{
    cin >> n >> m;
    vector<pair<int, int> > es(m);
    for (int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        x--; y--;
        es[i] = {x, y};
        g[x].push_back({y, i});
        g[y].push_back({x, i});
    }
    int now = n;
    for (int i = 0; i < n; i++)
    {
        if (!used[i])
        {
            int was_cnt = timer;
            dfs0(i, -1);
            int dif = timer - was_cnt;
            ans += dif * 1ll * (dif - 1) * (dif - 2);
            while (q.size() > 0)
            {
                int j = q.front();
                q.pop_front();
                arr.clear();
                arr.push_back(j);
                dfs1(es[j].first);
                dfs1(es[j].second);
                set<int> st;
                for (auto& j : arr)
                {
                    st.insert(es[j].first);
                    st.insert(es[j].second);
                }
                for (auto& u : st)
                {
                    gr[u].push_back(now);
                    gr[now].push_back(u);
                }
                now++;
            }
        }
    }
    fill(used, used + MAXK, 0);
    for (int i = n; i < now; i++)
    {
        if (!used[i])
        {
            dfs2(i, -1);
            all = sz[i];
            dfs3(i, -1);
        }
    }
    cout << ans;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    t = 1;
    while (t--)
    {
        solve();
    }
    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