Submission #864595

#	Time	Username	Problem	Language	Result	Execution time	Memory
864595		boris_mihov	Duathlon (APIO18_duathlon)	C++17	31 / 100	172 ms	50812 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];
bool vis2[MAXN];
bool vis3[MAXN];
bool vis4[MAXN];
int compCntBCC;
int inComp[MAXN];
int inComp2[MAXN];
int compSz[MAXN];
int BCCcompSz[MAXN];
int t[MAXN], low[MAXN], timer;
int t2[MAXN], low2[MAXN], timer2;
std::set <std::pair <int,int>> bridges;
std::set <std::pair <int,int>> BCCedges;
std::vector <int> bcc[MAXN];
std::vector <int> g[MAXN];
std::vector <int> v[MAXN];
std::vector <int> active;
bool isART[MAXN];

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

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

        if (vis2[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 neigh = 0;
    vis3[node] = true;
    for (const int &u : v[node])
    {
        if (!vis3[node])
        {
            calcANS(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) * (active.size() - compSz[node]) * 2;
    ans += 1LL * compSz[node] * (compSz[node] - 1) * neigh;
}

void calcANS2(int node, int par)
{
    // std::cout << "calc ans2: " << node << ' ' << par << '\n';
    vis4[node] = true;
    t2[node] = low2[node] = ++timer2;
    sz[node] = compSz[node];
    int maxEdge = 0;

    int out = 0;
    std::vector <int> sizes;
    for (const int &u : v[node])
    {
        if (u == par)
        {
            continue;
        }

        if (vis4[u])
        {
            low2[node] = std::min(low2[node], t2[u]);
            continue;
        }
        
        calcANS2(u, node);
        sz[node] += sz[u];
        sizes.push_back(sz[u]);
        low2[node] = std::min(low2[node], low2[u]);
    }   

    // std::cout << "done: " << node << ' ' << sz[node] << ' ' << out << '\n';
    out += active.size() - sz[node];
    sizes.push_back(out);

    llong prefix = 0;
    for (const int &currSz : sizes)
    {
        ans += prefix * currSz * 2;
        prefix += currSz;
    }
}

void solve()
{
    for (int node = 1 ; node <= n ; ++node)
    {
        if (vis2[node])
        {
            continue;
        }

        active.clear();
        findBridges(node, 0);
        for (const int &i : active)
        {
            if (!vis[i])
            {
                compCnt++;
                findBCC(i);
            }
        }

        for (const int &from : active)
        {
            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(compCnt);
        // std::cout << "before calc2: " << ans << '\n';
        calcANS2(compCnt, 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;
}

/*
9 12
1 2
2 3
3 1
4 5
5 6
6 4
7 8
8 9
9 7
3 9
3 6
6 9
*/

Compilation message (stderr)

count_triplets.cpp: In function 'void calcANS2(int, int)':
count_triplets.cpp:124:9: warning: unused variable 'maxEdge' [-Wunused-variable]
  124 |     int maxEdge = 0;
      |         ^~~~~~~

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