oj.uz

Submission #897575

# Submission time Handle Problem Language Result Execution time Memory
897575 2024-01-03T12:36:00 Z davitmarg Duathlon (APIO18_duathlon) C++17
0 / 100
 180 ms 123084 KB 
//DavitMarg

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <random>
#include <chrono>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair    
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;

const int N = 500005;


int n, m, used[N], art[N];
int a[N], b[N];
vector<pair<int,int>> g[N];
int tin[N], tout[N], low[N], timer;
int color[N], col;
set<int> s[N], colors[N];;
vector<int> comp;

void addComp(int ind = 0)
{
    if (comp.empty())
        return;
    col++;
    while (!comp.empty())
    {
        int j = comp.back();
        s[col].insert(a[j]);
        s[col].insert(b[j]);

        colors[a[j]].insert(col);
        colors[b[j]].insert(col);

        comp.pop_back();
        if (j == ind)
            break;
    }
}

void dfs(int v, int p)
{
    tin[v] = ++timer;
    used[v] = 1;
    low[v] = tin[v];
    int children = 0;
    for (int j = 0; j < g[v].size(); j++)
    {
        int to = g[v][j].first;
        int ind = g[v][j].second;

        if (to == p)
            continue;
        if (used[to])
        {
            low[v] = min(low[v], tin[to]);
            if(low[to] < tin[v])
                comp.push_back(ind);
            continue;
        }
        children++;
        comp.push_back(ind);
        dfs(to, v);

        if (low[to] >= tin[v])
        {
            art[v] = 1;
            addComp(ind);
        }

        low[v] = min(low[v], low[to]);
    }

    if (p == 0)
    {
        art[v] = (children > 1);
        addComp();
    }
}


int k;
LL sz[N], sb[N], ans, sum;
vector<int> G[N];

void dfs2(int v, int p)
{
    used[v] = 1;
    sb[v] = sz[v];
    vector<LL> sizes;
    for (int to : G[v])
    {
        if (to == p)
            continue;
        dfs2(to, v);
        sb[v] += sb[to];
        sizes.push_back(sb[to]);
    }

    LL psize = sum - sb[v];
    if (psize)
        sizes.push_back(psize);

    if (v <= k)
    {
        LL pref = 0;
        for (int i = 0; i < sizes.size(); i++)
        {
            ans += pref * sizes[i] * 2ll;
            pref += sizes[i];
        }
    }
    else
    { 
        LL x = sz[v];
        LL y = G[v].size();

        LL pref = 0;
        for (int i = 0; i < sizes.size(); i++)
        {
            ans += pref * (sizes[i] + 1ll) * 2ll * x;
            pref += sizes[i] + 1;
        }

        for (int i = 0; i < sizes.size(); i++)
        {
            ans += sizes[i] * x * (x - 1ll);
        }
    }
    
}


void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i] >> b[i];
        g[a[i]].push_back(MP(b[i], i));
        g[b[i]].push_back(MP(a[i], i));
    }

    for(int i = 1; i <= n; i++)
        if(!used[i])
            dfs(i, 0);

    vector<int> ar;

    for (int i = 1; i <= n; i++)
    {
        if (art[i])
            ar.push_back(i);
        used[i] = 0;
    }

    k = ar.size();



    sum = n;

    for (int i = 1; i <= col; i++)
    {
        LL x = s[i].size();
        sz[k + i] = s[i].size();
        ans += x * (x - 1ll) * (x - 2ll);
    }

    for (int j = 0; j < k; j++)
    {
        int v = ar[j];

        int x = j + 1;

        sz[x] = 1ll;
        for (auto it = colors[v].begin(); it != colors[v].end(); ++it)
        {
            int y = (*it) + k;
            sz[y]--;

            G[x].push_back(y);
            G[y].push_back(x);
        }
        
    }


    for (int i = 1; i <= k; i++)
    {
        if (used[i])
            continue;
        dfs2(i, 0);
    }

    cout << ans << endl;
}

int main()
{
    fastIO;
    int T = 1;
    //cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

/*


4 3
1 2
2 3
3 4

4 4
1 2
2 3
3 4
4 2

8 10
1 2
2 3
3 1
1 5
5 6
6 1
1 7
7 8
8 1
9 8

*/

Compilation message

count_triplets.cpp: In function 'void dfs(int, int)':
count_triplets.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int j = 0; j < g[v].size(); j++)
      |                     ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs2(int, int)':
count_triplets.cpp:127:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         for (int i = 0; i < sizes.size(); i++)
      |                         ~~^~~~~~~~~~~~~~
count_triplets.cpp:139:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |         for (int i = 0; i < sizes.size(); i++)
      |                         ~~^~~~~~~~~~~~~~
count_triplets.cpp:145:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |         for (int i = 0; i < sizes.size(); i++)
      |                         ~~^~~~~~~~~~~~~~
count_triplets.cpp:136:12: warning: unused variable 'y' [-Wunused-variable]
  136 |         LL y = G[v].size();
      |            ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 73816 KB Output is correct
2 Correct 19 ms 73612 KB Output is correct
3 Correct 20 ms 73564 KB Output is correct
4 Correct 20 ms 73560 KB Output is correct
5 Correct 20 ms 73564 KB Output is correct
6 Correct 20 ms 73820 KB Output is correct
7 Incorrect 19 ms 73820 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 73816 KB Output is correct
2 Correct 19 ms 73612 KB Output is correct
3 Correct 20 ms 73564 KB Output is correct
4 Correct 20 ms 73560 KB Output is correct
5 Correct 20 ms 73564 KB Output is correct
6 Correct 20 ms 73820 KB Output is correct
7 Incorrect 19 ms 73820 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 100536 KB Output is correct
2 Correct 109 ms 100556 KB Output is correct
3 Incorrect 136 ms 109712 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 74076 KB Output is correct
2 Correct 20 ms 74076 KB Output is correct
3 Correct 20 ms 74328 KB Output is correct
4 Correct 21 ms 74256 KB Output is correct
5 Correct 21 ms 74076 KB Output is correct
6 Correct 23 ms 74244 KB Output is correct
7 Correct 21 ms 74324 KB Output is correct
8 Correct 20 ms 74076 KB Output is correct
9 Correct 21 ms 74136 KB Output is correct
10 Incorrect 21 ms 73940 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 107208 KB Output is correct
2 Correct 137 ms 107212 KB Output is correct
3 Correct 134 ms 107028 KB Output is correct
4 Correct 148 ms 108496 KB Output is correct
5 Correct 162 ms 107220 KB Output is correct
6 Correct 180 ms 123084 KB Output is correct
7 Correct 172 ms 117652 KB Output is correct
8 Correct 166 ms 116684 KB Output is correct
9 Correct 173 ms 113908 KB Output is correct
10 Incorrect 137 ms 107084 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 107416 KB Output is correct
2 Correct 145 ms 107460 KB Output is correct
3 Incorrect 142 ms 105392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 73816 KB Output is correct
2 Correct 19 ms 73612 KB Output is correct
3 Correct 20 ms 73564 KB Output is correct
4 Correct 20 ms 73560 KB Output is correct
5 Correct 20 ms 73564 KB Output is correct
6 Correct 20 ms 73820 KB Output is correct
7 Incorrect 19 ms 73820 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 73816 KB Output is correct
2 Correct 19 ms 73612 KB Output is correct
3 Correct 20 ms 73564 KB Output is correct
4 Correct 20 ms 73560 KB Output is correct
5 Correct 20 ms 73564 KB Output is correct
6 Correct 20 ms 73820 KB Output is correct
7 Incorrect 19 ms 73820 KB Output isn't correct
8 Halted 0 ms 0 KB -