Submission #1127346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127346		_shr104	Duathlon (APIO18_duathlon)	C++20	100 / 100	166 ms	36424 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 2e5+7;
struct block_cut_tree
{
    ll n, m, tdfs = 0, node_id = 0;
    vector<ll> num, low, id, sz;
    vector<bool> is_cutpoint, ck;
    vector<vector<ll>> c, start_g, g;  
    stack<ll> stk;
    block_cut_tree() {}
    block_cut_tree(ll nn, ll mm) 
    {
        n = nn; m = mm;
        start_g.resize(n+7); num.resize(n+7); 
        low.resize(n+7); is_cutpoint.resize(n+7);
        id.resize(n+7); sz.resize(2*n+7); ck.resize(2*n+7);
    }
    void get_graph()
    {
        for (ll i = 1; i <= m; i++)
        {
            ll a, b; cin >> a >> b;
            start_g[a].pb(b); start_g[b].pb(a);
        }
    }
    void find_2cc(ll u, ll v)
    {
        num[u] = low[u] = ++tdfs; stk.push(u);
        for (ll i : start_g[u])
        {
            if (i != v)
            {
                if (!num[i])
                {
                    find_2cc(i,u);
                    low[u] = min(low[u],low[i]);
                    if (low[i] >= num[u])
                    {
                        is_cutpoint[u] = (num[u] > 1 || num[i] > 2);
                        c.pb({u}); while (c.back().back() != i) c.back().pb(stk.top()), stk.pop();
                    }
                } 
                else low[u] = min(low[u],num[i]);
            }
        }
    }
    void build()
    {
        for (ll i = 1; i <= n; i++) {if (!num[i]) {find_2cc(i,i);}} g.pb({});
        for (ll i = 1; i <= n; i++) {if (is_cutpoint[i]) {id[i] = ++node_id; sz[id[i]]++; ck[id[i]] = 1; g.pb({});}}
        for (vector<ll> i : c)
        {
            ll node = ++node_id; g.pb({});
            for (ll u : i)
            {
                if (!is_cutpoint[u]) {id[u] = node; sz[id[u]]++;}
                else {g[node].pb(id[u]), g[id[u]].pb(node);}
            }
        }
    }
};
ll n, m, sz[mxn], ans = 0;
bool vis[mxn];
block_cut_tree bct;
void dfs(ll u, ll v)
{
    sz[u] = bct.sz[u]; vis[u] = 1;
    for (ll i : bct.g[u])
    {
        if (i != v)
        {
            dfs(i,u);
            sz[u] += sz[i];
        }
    }
}
void dfs_ans(ll u, ll v, ll root)
{
    if (bct.ck[u])
    {
        for (ll i : bct.g[u])
        {
            if (i != v) ans -= (bct.sz[i]+bct.g[i].size()-1)*(sz[root]-sz[i])*(sz[root]-sz[i]-1);
            else ans -= (bct.sz[i]+bct.g[i].size()-1)*sz[u]*(sz[u]-1);
        }
    }
    for (ll i : bct.g[u]) 
    {
        if (i != v) dfs_ans(i,u,root);
    }
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
    cin >> n >> m; bct = block_cut_tree(n,m); bct.get_graph(); bct.build();
    for (ll i = 1; i <= bct.node_id; i++) 
    {
        if (!vis[i])
        {
            dfs(i,i);
            ans += sz[i]*(sz[i]-1)*(sz[i]-2);
            dfs_ans(i,i,i);
        }
    }
    cout << ans;
}

• 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