Submission #864580

#	Time	Username	Problem	Language	Result	Execution time	Memory
864580		boris_mihov	Duathlon (APIO18_duathlon)	C++17	0 / 100	136 ms	32568 KiB

count_triplets

#include <algorithm>
#include <iostream>
#include <cassert>
#include <chrono>
#include <vector>
#include <random>
#include <stack>
#include <queue>
#include <set>
#include <map>

#ifdef DEVAL
    #define cerr if (false) cerr
#endif

typedef long long llong;
const int MAXN = 100000 + 10;
const int INF  = 1e9;

std::mt19937 rngNow(std::chrono::high_resolution_clock::now().time_since_epoch().count());
std::mt19937 rng(69420);

int n, m;
int compCnt;
int sz[MAXN];
bool vis[MAXN];
int inComp[MAXN];
int compSz[MAXN];
int t[MAXN], low[MAXN], timer;
std::set <std::pair <int,int>> bridges;
std::set <std::pair <int,int>> BCCedges;
std::vector <int> g[MAXN];
std::vector <int> v[MAXN];
bool isART[MAXN];

void findBridges(int node, int par)
{
    vis[node] = true;
    t[node] = low[node] = ++timer;
    int maxEdge = 0;

    for (const int &u : g[node])
    {
        if (u == par)
        {
            continue;
        }

        if (vis[u])
        {
            low[node] = std::min(low[node], t[u]);
            continue;
        }
        
        findBridges(u, node);
        maxEdge = std::max(maxEdge, low[u]);
        if (low[u] > t[node])
        {
            bridges.insert({node, u});
            bridges.insert({u, node});
        }

        low[node] = std::min(low[node], low[u]);
    }

    if (maxEdge >= t[node])
    {
        isART[node] = true;
    }
}

void findBCC(int node)
{
    vis[node] = true;
    inComp[node] = compCnt;
    compSz[inComp[node]]++;
    for (const int &u : g[node])
    {
        if (isART[u] || isART[node] || vis[u])
        {
            continue;
        }

        findBCC(u);
    }
}

llong ans;
void calcANS(int node, int par)
{
    sz[node] = compSz[node];
    int neigh = compSz[par];
    for (const int &u : v[node])
    {
        if (u == par)
        {
            continue;
        }

        calcANS(u, node);
        sz[node] += sz[u];
        neigh += compSz[u];
    } 

    if (compSz[node] > 2) ans += 1LL * compSz[node] * (compSz[node] - 1) * (compSz[node] - 2);
    ans += 1LL * compSz[node] * (compSz[node] - 1) * (n - compSz[node]) * 2;
    ans += 1LL * compSz[node] * (sz[node] - compSz[node]) * (n - sz[node]) * 2;
    ans += 1LL * compSz[node] * (compSz[node] - 1) * neigh;
}

void solve()
{
    findBridges(1, 0);
    for (int i = 1 ; i <= n ; ++i)
    {
        assert(vis[i]);
    }   

    std::fill(vis + 1, vis + 1 + n, false);
    for (int i = 1 ; i <= n ; ++i)
    {
        if (!vis[i])
        {
            compCnt++;
            findBCC(i);
        }
    }

    for (int from = 1 ; from <= n ; ++from)
    {
        for (const int &to : g[from])
        {
            if (inComp[from] == inComp[to] || BCCedges.count({inComp[from], inComp[to]}))
            {
                continue;
            }

            BCCedges.insert({inComp[from], inComp[to]});
            // std::cout << "add edge: " << inComp[from] << ' ' << inCom
            v[inComp[from]].push_back(inComp[to]);
        }
    }

    calcANS(1, 0);
    std::cout << ans << '\n';
}


void input()
{
    std::cin >> n >> m;
    for (int i = 1 ; i <= m ; ++i)
    {
        int u, v;
        std::cin >> u >> v;
        if (u == v)
        {
            continue;
        }

        g[u].push_back(v);
        g[v].push_back(u);
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10