제출 #864583

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
864583		boris_mihov	철인 이종 경기 (APIO18_duathlon)	C++17	8 / 100	613 ms	1048576 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];
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];
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 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) * (active.size() - compSz[node]) * 2;
    ans += 1LL * compSz[node] * (sz[node] - compSz[node]) * (active.size() - sz[node]) * 2;
    ans += 1LL * compSz[node] * (compSz[node] - 1) * neigh;
}

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, 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: 8 / 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