Submission #988422

#	Time	Username	Problem	Language	Result	Execution time	Memory
988422		876pol	Duathlon (APIO18_duathlon)	C++17	0 / 100	168 ms	46852 KiB

count_triplets

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using pll = pair<ll, ll>;
template <class T>
using vec = vector<T>;
template <class T>
using indexed_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define FOR(i, s, e) for (ll i = (ll)s; i < e; i++)
#define CFOR(i, s, e) for (ll i = (ll)s; i <= e; i++)
#define TRAV(e, a) for (const auto &e : a)
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << "ln" << __LINE__ << ": " << #x << " = " << x << endl;

template <class T, class = decay_t<decltype(*begin(declval<T>()))>,
          class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &out, const T &obj) {
    out << "[";
    for (auto it = obj.begin(); it != obj.end(); it++) {
        out << &", "[2 * (it == obj.begin())] << *it;
    }
    return out << "]";
}

template <class K, class V>
ostream &operator<<(ostream &out, const pair<K, V> &obj) {
    return out << "(" << obj.first << ", " << obj.second << ")";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n, m;
    cin >> n >> m;
    vec<vec<ll>> graph(n + 1);
    FOR(i, 0, m) {
        ll a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    ll ans = 0;
    vec<ll> tin(n + 1), low(n + 1), visited(n + 1), is_cut(n + 1);
    ll tm = 0;
    CFOR(root, 1, n) {
        vec<pll> comp;
        vec<ll> arti;
        vec<vec<ll>> blocks;
        function<void(ll, ll)> dfs1 = [&](ll curr, ll prev) {
            low[curr] = tin[curr] = tm++;
            visited[curr] = 1;
            ll ch = 0;
            TRAV(e, graph[curr]) {
                if (e == prev) continue;
                if (visited[e]) {
                    low[curr] = min(low[curr], tin[e]);
                    if (tin[e] < tin[curr]) comp.push_back({curr, e});
                } else {
                    comp.push_back({curr, e});
                    dfs1(e, curr);
                    low[curr] = min(low[curr], low[e]);
                    ch++;
                    if (tin[curr] <= low[e] && curr != root) {
                        arti.push_back(curr);
                        is_cut[curr] = 1;
                    }
                    if (tin[curr] <= low[e] || curr == root) {
                        blocks.push_back({});
                        vec<ll> &obj = blocks.back();
                        while (comp.back() != pll{curr, e}) {
                            obj.push_back(comp.back().first);
                            obj.push_back(comp.back().second);
                            comp.pop_back();
                        }
                        obj.push_back(comp.back().first);
                        obj.push_back(comp.back().second);
                        comp.pop_back();
                        sort(all(obj));
                        obj.erase(unique(all(obj)), obj.end());
                    }
                }
            }
            if (curr == root && ch > 1) {
                arti.push_back(curr);
                is_cut[curr] = 1;
            }
        };
        if (visited[root]) continue;
        dfs1(root, 0);
        sort(all(arti));
        arti.erase(unique(all(arti)), arti.end());
        ll gsize = arti.size() + blocks.size();
        vec<vec<ll>> cgraph(gsize);
        vec<ll> nn(gsize);
        FOR(i, 0, blocks.size()) {
            TRAV(e, blocks[i]) {
                if (!is_cut[e]) continue;
                ll cnode = lower_bound(all(arti), e) - arti.begin();
                cgraph[cnode].push_back(arti.size() + i);
                cgraph[arti.size() + i].push_back(cnode);
            }
            nn[arti.size() + i] = blocks[i].size();
        }
        // dbg(arti);
        // dbg(blocks);
        // dbg(cgraph);
        // dbg(nn);
        vec<ll> ssize(gsize);
        function<void(ll, ll)> dfs2 = [&](ll curr, ll prev) {
            ssize[curr] = max(0ll, nn[curr] - 1);
            TRAV(e, cgraph[curr]) {
                if (e == prev) continue;
                dfs2(e, curr);
                ssize[curr] += ssize[e];
            }
        };
        dfs2(gsize - 1, -1);
        ll tsize = ssize[gsize - 1] + 1;
        // dbg(ssize);
        function<void(ll, ll)> dfs3 = [&](ll curr, ll prev) {
            ll psize = tsize - nn[curr];
            vec<ll> bs;
            TRAV(e, cgraph[curr]) {
                if (e == prev) continue;
                dfs3(e, curr);
                bs.push_back(ssize[e]);
                psize -= ssize[e];
            }
            if (nn[curr]) {
                if (psize) bs.push_back(psize);
                ans += nn[curr] * (nn[curr] - 1) * (nn[curr] - 2);
                ll sm = accumulate(all(bs), 0ll);
                TRAV(e, bs) ans += e * (sm - e) * nn[curr];
                TRAV(e, bs) {
                    ans += 2 * (nn[curr] - 1) * e;
                    ans += 2 * (nn[curr] - 1) * (nn[curr] - 2) * e;
                }
            } else {
                assert(psize > 1);
                bs.push_back(psize - 1);
                ll sm = accumulate(all(bs), 0ll);
                TRAV(e, bs) ans -= e * (sm - e);
            }
        };
        dfs3(gsize - 1, -1);
    }
    cout << ans << "\n";
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:17:43: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int, std::allocator<long long int> >, std::allocator<std::vector<long long int, std::allocator<long long int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define FOR(i, s, e) for (ll i = (ll)s; i < e; i++)
......
  105 |         FOR(i, 0, blocks.size()) {
      |             ~~~~~~~~~~~~~~~~~~~            
count_triplets.cpp:105:9: note: in expansion of macro 'FOR'
  105 |         FOR(i, 0, blocks.size()) {
      |         ^~~

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