Submission #900487

#	Time	Username	Problem	Language	Result	Execution time	Memory
900487		shmax	Duathlon (APIO18_duathlon)	C++14	23 / 100	981 ms	1048576 KiB

count_triplets

/*
 * powered by ANDRIY POPYK
 * in honor of MYSELF and SEGMENT DECOMPOSITION and N^(log(N)) and (Harry Potter and the Methods of Rationality) and Monkie D. Luffy
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt")

using namespace std;
using namespace __gnu_pbds;
#define int long long
#define float long double
#define elif else if
#define endl "\n"
#define mod 1000000007
#define pi acos(-1)
#define eps 0.000000001
#define inf 1000'000'000'000'000'000LL
#define FIXED(a) cout << fixed << setprecision(a)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define time_init auto start = std::chrono::high_resolution_clock::now()
#define time_report                                       \
    auto end = std::chrono::high_resolution_clock::now(); \
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << endl
#define debug(x) \
    { cerr << #x << " = " << x << endl; }
#define len(x) (int) x.size()
#define sqr(x) ((x) * (x))
#define cube(x) ((x) * (x) * (x))
#define bit(x, i) (((x) >> (i)) & 1)
#define set_bit(x, i) ((x) | (1LL << (i)))
#define clear_bit(x, i) ((x) & (~(1LL << (i))))
#define toggle_bit(x, i) ((x) ^ (1LL << (i)))
#define low_bit(x) ((x) & (-(x)))
#define count_bit(x) __builtin_popcountll(x)
#define srt(x) sort(all(x))
#define rsrt(x) sort(rall(x))
#define mp make_pair
#define maxel(x) (*max_element(all(x)))
#define minel(x) (*min_element(all(x)))
#define maxelpos(x) (max_element(all(x)) - x.begin())
#define minelpos(x) (min_element(all(x)) - x.begin())
#define sum(x) (accumulate(all(x), 0LL))
#define product(x) (accumulate(all(x), 1LL, multiplies<int>()))
#define gcd __gcd
#define lcm(a, b) ((a) / gcd(a, b) * (b))
#define rev(x) (reverse(all(x)))
#define shift_left(x, k) (rotate(x.begin(), x.begin() + k, x.end()))
#define shift_right(x, k) (rotate(x.rbegin(), x.rbegin() + k, x.rend()))
#define is_sorted(x) (is_sorted_until(all(x)) == x.end())
#define is_even(x) (((x) &1) == 0)
#define is_odd(x) (((x) &1) == 1)
#define pow2(x) (1LL << (x))

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using matrix = vector<vector<T>>;
template<typename T>
using graph = vector<vector<T>>;
using hashmap = gp_hash_table<int, int, custom_hash>;

template<typename T>
vector<T> vect(int n, T val) {
    return vector<T>(n, val);
}

template<typename T>
vector<vector<T>> vect(int n, int m, T val) {
    return vector<vector<T>>(n, vector<T>(m, val));
}

template<typename T>
vector<vector<vector<T>>> vect(int n, int m, int k, T val) {
    return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, val)));
}

template<typename T>
vector<vector<vector<vector<T>>>> vect(int n, int m, int k, int l, T val) {
    return vector<vector<vector<vector<T>>>>(n, vector<vector<vector<T>>>(m, vector<vector<T>>(k, vector<T>(l, val))));
}

template<typename T>
matrix<T> new_matrix(int n, int m, T val) {
    return matrix<T>(n, vector<T>(m, val));
}

template<typename T>
graph<T> new_graph(int n) {
    return graph<T>(n);
}

template<class T, class S>
inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}

template<class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}

using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
template<typename T>
using vec = vector<T>;

using pII = pair<int, int>;
template<typename T>
using enumerated = pair<T, int>;

struct BlockCutTree {
public:
    graph<int> g;
    int timer, n;
    vec<int> fup, tin;
    vec<bool> used;
    vec<vec<pII>> edge_components;
    vec<int> components;
    vec<int> comp_vertices;
    vec<int> cut_points;
    vec<bool> is_cut_point;
    stack<pII> buffer;
    int component_cnt;

    void dfs(int v, int p) {
        tin[v] = fup[v] = timer++;
        used[v] = true;
        bool is_cut = false;
        int child_cnt = 0;
        for (auto u: g[v]) {
            if (u == p)
                continue;
            if (!used[u]) {
                child_cnt++;
                buffer.emplace(v, u);
                dfs(u, v);
                if (fup[u] >= tin[v]) {
                    is_cut = true;
                    edge_components.emplace_back();
                    while (true) {
                        auto [a, b] = buffer.top();
                        buffer.pop();
                        edge_components.back().emplace_back(a, b);
                        if (a == v && b == u) {
                            break;
                        }
                    }
                }
                chmin(fup[v], fup[u]);
            } else {
                chmin(fup[v], tin[u]);
                if (tin[u] < tin[v]) {
                    buffer.emplace(v, u);
                }
            }
        }
        if (p == -1) {
            is_cut = child_cnt > 1;
        }
        if (is_cut) {
            cut_points.push_back(v);
            is_cut_point[v] = true;
        }
    }

    void build_components() {
        for (int i = 0; i < n; ++i) {
            if (!used[i]) {
                dfs(i, -1);
            }
        }
        components = vec<int>(n);
        component_cnt = 0;
        for (auto cp: cut_points) {
            components[cp] = component_cnt++;
        }
        for (auto &ec: edge_components) {
            for (auto [u, v]: ec) {
                if (!is_cut_point[u])
                    components[u] = component_cnt;
                if (!is_cut_point[v])
                    components[v] = component_cnt;
            }
//            if (was)
            component_cnt++;
        }

        comp_vertices.resize(component_cnt);
        for (int i = 0; i < n; ++i) {
            comp_vertices[components[i]]++;
        }
    }

    graph<int> bc_tree;

    void build_tree() {
        bc_tree = graph<int>(component_cnt);
        set<pair<int, int>> bc_tree_edges;
        int id = len(cut_points) - 1;
        for (const auto &eg: edge_components) {
            id++;
            for (auto [u, v]: eg) {
                if (is_cut_point[u]) {
//                    bc_tree_edges[components[u]].insert(id);
//                    bc_tree_edges[id].insert(components[u]);
                    int v_u = components[u];
                    int v_v = id;
                    if (v_u > v_v) {
                        swap(v_u, v_v);
                    }
                    bc_tree_edges.emplace(v_u, v_v);
                }
                if (is_cut_point[v]) {
                    int v_u = components[v];
                    int v_v = id;
                    if (v_u > v_v) {
                        swap(v_u, v_v);
                    }
                    bc_tree_edges.emplace(v_u, v_v);
                }
            }
        }
//        for (int i = 0; i < component_cnt; ++i) {
//            for (auto to: bc_tree_edges[i]) {
//                bc_tree[i].push_back(to);
//            }
//        }
        for (auto [u, v]: bc_tree_edges) {
            bc_tree[u].push_back(v);
            bc_tree[v].push_back(u);
        }
    }

    BlockCutTree(graph<int> &g) : g(g) {
        n = len(g);
        timer = 0;
        fup = tin = vec<int>(n);
        used = vec<bool>(n);
        is_cut_point = vec<bool>(n);
    }

    void print() {
        set<pII> edges;
        for (int i = 0; i < component_cnt; ++i) {
            for (auto to: bc_tree[i]) {
                if (edges.count({i, to}) or edges.count({to, i})) {
                    continue;
                }
                edges.emplace(i, to);
            }
        }
        cout << len(edges) << endl;
        for (auto [u, v]: edges) {
            cout << u + 1 << " " << v + 1 << endl;
        }
    }
};


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    i64 n, m;
    cin >> n >> m;
    graph<int> g(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v, --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    int all = 0;
    vec<int> sizes(n, 0);
    vec<bool> was(n, false);
    function<int(int, int)> calc_cur_size = [&](int v, int p) {
        int sum = 1;
        for (auto u: g[v]) {
            if (u != p)
                sum += calc_cur_size(u, v);
        }
        return sum;
    };

    int ttn = n;

    function<void(int, int)> dfs = [&](int v, int p) {
        if (was[v]) return;
        was[v] = true;
        sizes[v] = 1;
        for (auto u: g[v]) {
            if (u == p) continue;
            dfs(u, v);
            sizes[v] += sizes[u];
        }
        int top = ttn - sizes[v];
        all += top * (sizes[v] - 1) * 2;

        for (auto u: g[v]) {
            if (u == p) continue;
            int tn = sizes[v] - 1 - sizes[u];
            all += tn * sizes[u];
        }
    };

//    BlockCutTree bct(g);
//    bct.build_components();
//    bct.build_tree();
////    bct.print();
////    cout << endl;
//    i64 all = 0;
//    int dn = len(bct.bc_tree);
//    vec<int> sizes(dn, 0);
//    vec<bool> was(dn, false);
//    function<void(int, int)> dfs = [&](int v, int p) {
//        if (was[v]) return;
//        was[v] = true;
//        sizes[v] = bct.comp_vertices[v];
//        for (auto u: bct.bc_tree[v]) {
//            if (u == p)
//                continue;
//            dfs(u, v);
//            sizes[v] += sizes[u];
//        }
//        if (bct.comp_vertices[v] >= 3) {
//            int tc = bct.comp_vertices[v];
//            all += tc * (tc - 1) * (tc - 2);
//        }
//        if (bct.comp_vertices[v] >= 2) {
//            int tc = bct.comp_vertices[v];
//            int top = n - sizes[v];
//            all += tc * (tc - 1) * top * 2;
//        }
//        int top = n - sizes[v];
//        int tc = bct.comp_vertices[v];
//
//
//        for (auto u: bct.bc_tree[v]) {
//            if (u == p)
//                continue;
//            all += top * tc * sizes[u] * 2;
//            all += tc * (tc - 1) * sizes[u] * 2;
//            all += bct.comp_vertices[u] * (bct.comp_vertices[u] - 1) * tc;
//            int dc = sizes[v] - sizes[u] - tc;
//            all += tc * dc * sizes[u];
//        }
//    };
    for (int i = 0; i < n; i++) {
        if (!was[i]) {
            ttn = calc_cur_size(i, -1);
            dfs(i, -1);
        }
    }
    cout << all << endl;

}

Compilation message (stderr)

count_triplets.cpp: In member function 'void BlockCutTree::dfs(long long int, long long int)':
count_triplets.cpp:174:30: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  174 |                         auto [a, b] = buffer.top();
      |                              ^
count_triplets.cpp: In member function 'void BlockCutTree::build_components()':
count_triplets.cpp:211:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  211 |             for (auto [u, v]: ec) {
      |                       ^
count_triplets.cpp: In member function 'void BlockCutTree::build_tree()':
count_triplets.cpp:235:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  235 |             for (auto [u, v]: eg) {
      |                       ^
count_triplets.cpp:261:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  261 |         for (auto [u, v]: bc_tree_edges) {
      |                   ^
count_triplets.cpp: In member function 'void BlockCutTree::print()':
count_triplets.cpp:286:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  286 |         for (auto [u, v]: edges) {
      |                   ^

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