oj.uz

Submission #864594

# Submission time Handle Problem Language Result Execution time Memory
864594 2023-10-23T09:50:54 Z boris_mihov Duathlon (APIO18_duathlon) C++17
31 / 100
 165 ms 66244 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
        {
            assert(false);
            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 10588 KB Output is correct
2 Correct 2 ms 10588 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 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Runtime error 9 ms 21620 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 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 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Runtime error 9 ms 21620 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 25548 KB Output is correct
2 Correct 39 ms 25540 KB Output is correct
3 Correct 89 ms 31692 KB Output is correct
4 Correct 62 ms 28104 KB Output is correct
5 Correct 67 ms 25804 KB Output is correct
6 Correct 99 ms 33568 KB Output is correct
7 Correct 98 ms 29976 KB Output is correct
8 Correct 101 ms 32040 KB Output is correct
9 Correct 95 ms 28752 KB Output is correct
10 Correct 83 ms 27520 KB Output is correct
11 Correct 81 ms 24900 KB Output is correct
12 Correct 77 ms 24656 KB Output is correct
13 Correct 74 ms 24664 KB Output is correct
14 Correct 74 ms 24144 KB Output is correct
15 Correct 65 ms 23124 KB Output is correct
16 Correct 59 ms 22676 KB Output is correct
17 Correct 6 ms 11356 KB Output is correct
18 Correct 8 ms 11356 KB Output is correct
19 Correct 6 ms 11356 KB Output is correct
20 Correct 6 ms 11356 KB Output is correct
21 Correct 6 ms 11356 KB Output is correct
22 Correct 6 ms 11460 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 11100 KB Output is correct
7 Correct 3 ms 11096 KB Output is correct
8 Correct 3 ms 11100 KB Output is correct
9 Correct 3 ms 11096 KB Output is correct
10 Correct 3 ms 10840 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 3 ms 10840 KB Output is correct
13 Correct 3 ms 10840 KB Output is correct
14 Correct 3 ms 10844 KB Output is correct
15 Correct 3 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 3 ms 11100 KB Output is correct
18 Correct 2 ms 11352 KB Output is correct
19 Correct 2 ms 11100 KB Output is correct
20 Correct 3 ms 11100 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 37084 KB Output is correct
2 Correct 138 ms 37064 KB Output is correct
3 Correct 139 ms 37072 KB Output is correct
4 Correct 138 ms 37020 KB Output is correct
5 Correct 145 ms 37060 KB Output is correct
6 Correct 159 ms 49352 KB Output is correct
7 Correct 165 ms 41672 KB Output is correct
8 Correct 144 ms 40392 KB Output is correct
9 Correct 145 ms 39484 KB Output is correct
10 Correct 143 ms 36816 KB Output is correct
11 Correct 141 ms 37064 KB Output is correct
12 Correct 151 ms 37180 KB Output is correct
13 Correct 146 ms 36616 KB Output is correct
14 Correct 142 ms 34580 KB Output is correct
15 Correct 127 ms 32340 KB Output is correct
16 Correct 79 ms 25452 KB Output is correct
17 Correct 136 ms 38236 KB Output is correct
18 Correct 139 ms 38204 KB Output is correct
19 Correct 136 ms 38244 KB Output is correct
20 Correct 143 ms 38088 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 10844 KB Output is correct
3 Runtime error 10 ms 22108 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 37072 KB Output is correct
2 Correct 140 ms 36864 KB Output is correct
3 Runtime error 125 ms 66244 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 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 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Runtime error 9 ms 21620 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 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 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Runtime error 9 ms 21620 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -