제출 #450098

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
450098		ymm	Duathlon (APIO18_duathlon)	C++17	57 / 100	1090 ms	35648 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 solve(int v)
{
    p[v] = -1;
    vec.clear();
    int l = cnt;
    ll n = (dfs(v), vec.size());
    int r = cnt;
    Loop(c,l,r)
    {
        ll fsum = 0;
        for(int v : vs[c])
        {
            ll sum = 1;
            for(int u : A[v])
                if(p[u] == v && cs[u].back() != c)
                    sum += stree[u];
            if(c != cs[v].back())
                sum += n - stree[v];
            fsum += sum*(sum-1);
        }
        cc[c] = fsum;
    }
    ll ans = 0;
    for(int v : vec)
    {
        ans += (n-1)*(n-2);
        ll fsum = 0;
        for(int c : cs[v])
        {
            ll sum = 1;
            for(int u : A[v])
                if(p[u] == v && cs[u].back() != c)
                    sum += stree[u];
            if(c != cs[v].back())
                sum += n - stree[v];
            fsum += cc[c] - sum*(sum-1);
        }
        ans -= fsum;
    }
    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: 0 / 13
• Subtask 6: 15 / 15
• Subtask 7: 0 / 20
• Subtask 8: 8 / 8
• Subtask 9: 0 / 10