oj.uz

Submission #864583

# Submission time Handle Problem Language Result Execution time Memory
864583 2023-10-23T09:21:50 Z boris_mihov Duathlon (APIO18_duathlon) C++17
8 / 100
 613 ms 1048576 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6708 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Runtime error 613 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6708 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Runtime error 613 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 22732 KB Output is correct
2 Correct 52 ms 22628 KB Output is correct
3 Correct 118 ms 28128 KB Output is correct
4 Correct 61 ms 25296 KB Output is correct
5 Correct 66 ms 22480 KB Output is correct
6 Correct 112 ms 28272 KB Output is correct
7 Correct 106 ms 26952 KB Output is correct
8 Correct 99 ms 27856 KB Output is correct
9 Correct 93 ms 25940 KB Output is correct
10 Correct 81 ms 24668 KB Output is correct
11 Correct 73 ms 21840 KB Output is correct
12 Correct 77 ms 21524 KB Output is correct
13 Correct 79 ms 21580 KB Output is correct
14 Correct 66 ms 21076 KB Output is correct
15 Correct 56 ms 19840 KB Output is correct
16 Correct 56 ms 19340 KB Output is correct
17 Correct 4 ms 7256 KB Output is correct
18 Correct 3 ms 7256 KB Output is correct
19 Correct 3 ms 7256 KB Output is correct
20 Correct 3 ms 7260 KB Output is correct
21 Correct 3 ms 7224 KB Output is correct
22 Correct 3 ms 7256 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 136 ms 34312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 34224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6708 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Runtime error 613 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6708 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Runtime error 613 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -