Submission #450163

#	Time	Username	Problem	Language	Result	Execution time	Memory
450163		ymm	Duathlon (APIO18_duathlon)	C++17	100 / 100	233 ms	57028 KiB

count_triplets

///
///    I have a dream and a piano
///

#define _USE_MATH_DEFINES
#define FAST ios::sync_with_stdio(false),cin.tie(0);
#include <bits/stdc++.h>
#define Loop(x, l, r) for(int x = (l); x < (r); ++x)
#define LoopR(x, l, r) for(int x = (r)-1; x >= (l); --x)
#define all(x) x.begin(), x.end()
#define Kill(x) exit((cout << (x) << '\n', 0))
#define YN(flag) ((flag)? "YES": "NO")
#define F first
#define S second
typedef          long long   ll;
typedef unsigned long long  ull;
typedef std::pair<int,int>  pii;
typedef std::pair<ll ,ll >  pll;
using namespace std;

const int N = 200'010;
vector<int> A[N];
vector<int> cs[N], vs[N]; int cnt = 0;

bool vis[N];
vector<int> st, vec;
int h[N];
int p[N];
ll stree[N];
tuple<int,int,int> dfs(int v)
{
    vis[v] = 1;
    int sum = 1;
    int tsum = 1;
    int mn = h[v];
    for(int u : A[v])
    {
        if(vis[u]) mn = min(mn, h[u]);
        else {
            auto [x, y, z] = dfs((h[u] = h[v]+1, p[u]=v, u));
            tsum += x;
            if(z >= h[v]) {
                vs[cnt].push_back(v);
                cs[v].push_back(cnt);
                while(y--)
                {
                    int w = st.back(); st.pop_back();
                    cs[w].push_back(cnt);
                    vs[cnt].push_back(w);
                }
                ++cnt;
            } else {
                mn = min(z, mn);
                sum += y;
            }
        }
    }
    stree[v] = tsum;
    st.push_back(v);
    vec.push_back(v);
    return {tsum, sum, mn};
}

ll cc[N]={};
ll vv[N]={};
ll hlp[N];
map<int,ll> hlpp[N];

ll solve(int v)
{
    p[v] = -1;
    vec.clear();
    ll n = (dfs(v), vec.size());

    for(int v : vec)
        for(int u : A[v])
            if(p[u] == v)
                hlp[v] += stree[u],
                hlpp[v][cs[u].back()] += stree[u];

    for(int v : vec)
    {
        for(int c : cs[v])
        {
            ll sum = 1 + hlp[v] - hlpp[v][c];
            if(c != cs[v].back())
                sum += n - stree[v];
            cc[c] += sum*(sum-1);
            vv[v] += sum*(sum-1);
        }
    }
    ll ans = 0;
    for(int v : vec)
    {
        ans += (n-1)*(n-2);
        for(int c : cs[v]) ans -= cc[c];
        ans += vv[v];
    }
    return ans;
}

int n, m;

int main()
{
    FAST;
    cin >> n >> m;
    Loop(i,0,m)
    {
        int v, u;
        cin >> v >> u;
        --v; --u;
        A[v].push_back(u);
        A[u].push_back(v);
    }
    ll ans = 0;
    Loop(i,0,n) if(!vis[i]) ans += solve(i);
    /*Loop(i,0,cnt)
    {
        for(int v : vs[i])
            cout << v << ' ';
        cout << '\n';
    }*/
    cout << ans << '\n';
}

• 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