oj.uz

Submission #864593

# Submission time Handle Problem Language Result Execution time Memory
864593 2023-10-23T09:49:13 Z boris_mihov Duathlon (APIO18_duathlon) C++17
31 / 100
 173 ms 50948 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];
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];
        if (low2[u] >= t2[node])
        {
            sizes.push_back(sz[u]);
        } else
        {
            out += 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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10816 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10808 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Incorrect 2 ms 10808 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10816 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10808 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Incorrect 2 ms 10808 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 25412 KB Output is correct
2 Correct 39 ms 25620 KB Output is correct
3 Correct 92 ms 32460 KB Output is correct
4 Correct 72 ms 28328 KB Output is correct
5 Correct 66 ms 26320 KB Output is correct
6 Correct 97 ms 34508 KB Output is correct
7 Correct 99 ms 30288 KB Output is correct
8 Correct 101 ms 32788 KB Output is correct
9 Correct 101 ms 29076 KB Output is correct
10 Correct 84 ms 27728 KB Output is correct
11 Correct 87 ms 24868 KB Output is correct
12 Correct 86 ms 24668 KB Output is correct
13 Correct 86 ms 24960 KB Output is correct
14 Correct 71 ms 24236 KB Output is correct
15 Correct 61 ms 23124 KB Output is correct
16 Correct 57 ms 22608 KB Output is correct
17 Correct 6 ms 11552 KB Output is correct
18 Correct 6 ms 11356 KB Output is correct
19 Correct 6 ms 11608 KB Output is correct
20 Correct 6 ms 11356 KB Output is correct
21 Correct 7 ms 11356 KB Output is correct
22 Correct 6 ms 11356 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10844 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 3 ms 11100 KB Output is correct
5 Correct 3 ms 11100 KB Output is correct
6 Correct 3 ms 10944 KB Output is correct
7 Correct 3 ms 11100 KB Output is correct
8 Correct 3 ms 11352 KB Output is correct
9 Correct 3 ms 11100 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 3 ms 10844 KB Output is correct
14 Correct 3 ms 10844 KB Output is correct
15 Correct 3 ms 10844 KB Output is correct
16 Correct 3 ms 10844 KB Output is correct
17 Correct 2 ms 11096 KB Output is correct
18 Correct 3 ms 11040 KB Output is correct
19 Correct 2 ms 11100 KB Output is correct
20 Correct 3 ms 11096 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 37060 KB Output is correct
2 Correct 137 ms 37068 KB Output is correct
3 Correct 140 ms 37068 KB Output is correct
4 Correct 145 ms 37064 KB Output is correct
5 Correct 139 ms 37064 KB Output is correct
6 Correct 173 ms 50948 KB Output is correct
7 Correct 150 ms 42380 KB Output is correct
8 Correct 141 ms 40908 KB Output is correct
9 Correct 150 ms 39620 KB Output is correct
10 Correct 138 ms 36744 KB Output is correct
11 Correct 153 ms 37192 KB Output is correct
12 Correct 140 ms 36692 KB Output is correct
13 Correct 141 ms 36688 KB Output is correct
14 Correct 139 ms 34644 KB Output is correct
15 Correct 124 ms 32432 KB Output is correct
16 Correct 75 ms 25424 KB Output is correct
17 Correct 128 ms 38212 KB Output is correct
18 Correct 132 ms 38220 KB Output is correct
19 Correct 140 ms 38504 KB Output is correct
20 Correct 134 ms 37888 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Correct 3 ms 10840 KB Output is correct
3 Incorrect 3 ms 10844 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 37128 KB Output is correct
2 Correct 137 ms 36844 KB Output is correct
3 Incorrect 118 ms 33220 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10816 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10808 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Incorrect 2 ms 10808 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10816 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10808 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Incorrect 2 ms 10808 KB Output isn't correct
8 Halted 0 ms 0 KB -