Submission #897697

#	Time	Username	Problem	Language	Result	Execution time	Memory
897697		davitmarg	Duathlon (APIO18_duathlon)	C++17	100 / 100	226 ms	135632 KiB

count_triplets

//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 x = sz[v];
        LL y = G[v].size();
        LL s = x + y;

        for (int i = 0; i < sizes.size(); i++)
        {
            LL subs = sizes[i];
            ans += (s - 1ll) * (subs - 0ll) * (subs - 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);
    }

    ans = -ans;
    for (int i = 1; i <= num; i++)
    {
        LL x = cnt[i];
        ans += x * (x - 1ll) * (x - 2ll);
    }

    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 6
1 2
2 3
3 4
5 6
6 7
7 8


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

5 5
1 2
2 3
3 4
4 2
3 5


1 2 4
1 2 3
1 2 5

3 2 4
4 2 5

*/

Compilation message (stderr)

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:132:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         for (int i = 0; i < sizes.size(); i++)
      |                         ~~^~~~~~~~~~~~~~
count_triplets.cpp: In function 'void solve()':
count_triplets.cpp:171:12: warning: unused variable 'x' [-Wunused-variable]
  171 |         LL x = s[i].size();
      |            ^

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 15 / 15
• Subtask 7: 20 / 20
• Subtask 8: 8 / 8
• Subtask 9: 10 / 10