oj.uz

Submission #897578

# Submission time Handle Problem Language Result Execution time Memory
897578 2024-01-03T12:41:42 Z davitmarg Duathlon (APIO18_duathlon) C++17
31 / 100
 210 ms 124328 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, cnt[N], num, comp[N];
set<int> s[N], colors[N];
vector<int> st;

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

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

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

void dfs(int v, int p)
{
    tin[v] = ++timer;
    used[v] = 1;
    low[v] = tin[v];
    comp[v] = num;
    cnt[num]++;
    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])
                st.push_back(ind);
            continue;
        }
        children++;
        st.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])
        {
            num++;
            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();

    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;
        int v = ar[i - 1];
        sum = cnt[comp[v]];
        dfs2(i, 0);
    }

    cout << ans << endl;
}

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

    return 0;
}

/*


8 6
1 2
2 3
3 4
5 6
6 7
7 8

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:69: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]
   69 |     for (int j = 0; j < g[v].size(); j++)
      |                     ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs2(int, int)':
count_triplets.cpp:129:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         for (int i = 0; i < sizes.size(); i++)
      |                         ~~^~~~~~~~~~~~~~
count_triplets.cpp:141:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |         for (int i = 0; i < sizes.size(); i++)
      |                         ~~^~~~~~~~~~~~~~
count_triplets.cpp:147:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         for (int i = 0; i < sizes.size(); i++)
      |                         ~~^~~~~~~~~~~~~~
count_triplets.cpp:138:12: warning: unused variable 'y' [-Wunused-variable]
  138 |         LL y = G[v].size();
      |            ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 73816 KB Output is correct
2 Correct 21 ms 73740 KB Output is correct
3 Correct 19 ms 73820 KB Output is correct
4 Correct 19 ms 73820 KB Output is correct
5 Correct 18 ms 73820 KB Output is correct
6 Correct 21 ms 73752 KB Output is correct
7 Incorrect 19 ms 73700 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 130 ms 100284 KB Output is correct
2 Correct 118 ms 100040 KB Output is correct
3 Correct 133 ms 109136 KB Output is correct
4 Correct 144 ms 102740 KB Output is correct
5 Correct 142 ms 102656 KB Output is correct
6 Correct 156 ms 108768 KB Output is correct
7 Correct 153 ms 105956 KB Output is correct
8 Correct 143 ms 106768 KB Output is correct
9 Correct 152 ms 103636 KB Output is correct
10 Correct 129 ms 103892 KB Output is correct
11 Correct 101 ms 94676 KB Output is correct
12 Correct 87 ms 94800 KB Output is correct
13 Correct 80 ms 92916 KB Output is correct
14 Correct 88 ms 92732 KB Output is correct
15 Correct 64 ms 89172 KB Output is correct
16 Correct 75 ms 88912 KB Output is correct
17 Correct 21 ms 75744 KB Output is correct
18 Correct 21 ms 75600 KB Output is correct
19 Correct 20 ms 75612 KB Output is correct
20 Correct 22 ms 75604 KB Output is correct
21 Correct 22 ms 75612 KB Output is correct
22 Correct 21 ms 75612 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 74076 KB Output is correct
2 Correct 20 ms 73944 KB Output is correct
3 Correct 23 ms 74076 KB Output is correct
4 Correct 20 ms 74328 KB Output is correct
5 Correct 20 ms 74072 KB Output is correct
6 Correct 23 ms 74076 KB Output is correct
7 Correct 20 ms 74072 KB Output is correct
8 Correct 25 ms 74076 KB Output is correct
9 Correct 21 ms 74328 KB Output is correct
10 Correct 21 ms 74076 KB Output is correct
11 Correct 20 ms 74156 KB Output is correct
12 Correct 20 ms 74072 KB Output is correct
13 Correct 20 ms 74076 KB Output is correct
14 Correct 19 ms 73968 KB Output is correct
15 Correct 21 ms 74076 KB Output is correct
16 Correct 19 ms 73816 KB Output is correct
17 Correct 20 ms 74076 KB Output is correct
18 Correct 20 ms 74076 KB Output is correct
19 Correct 19 ms 73944 KB Output is correct
20 Correct 23 ms 74112 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 107724 KB Output is correct
2 Correct 147 ms 107724 KB Output is correct
3 Correct 165 ms 106500 KB Output is correct
4 Correct 138 ms 106504 KB Output is correct
5 Correct 150 ms 107584 KB Output is correct
6 Correct 210 ms 124328 KB Output is correct
7 Correct 177 ms 118196 KB Output is correct
8 Correct 166 ms 117284 KB Output is correct
9 Correct 175 ms 114120 KB Output is correct
10 Correct 159 ms 107724 KB Output is correct
11 Correct 154 ms 108076 KB Output is correct
12 Correct 156 ms 107988 KB Output is correct
13 Correct 163 ms 108152 KB Output is correct
14 Correct 144 ms 105080 KB Output is correct
15 Correct 133 ms 102080 KB Output is correct
16 Correct 69 ms 90960 KB Output is correct
17 Correct 113 ms 107332 KB Output is correct
18 Correct 120 ms 107460 KB Output is correct
19 Correct 115 ms 109832 KB Output is correct
20 Correct 127 ms 107248 KB Output is correct

Subtask #6
0 / 15.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 Incorrect 21 ms 74072 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 107696 KB Output is correct
2 Correct 156 ms 107956 KB Output is correct
3 Incorrect 149 ms 105800 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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