oj.uz

Submission #988422

# Submission time Handle Problem Language Result Execution time Memory
988422 2024-05-24T16:40:40 Z 876pol Duathlon (APIO18_duathlon) C++17
0 / 100
 168 ms 46852 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 28868 KB Output is correct
2 Correct 71 ms 28896 KB Output is correct
3 Correct 105 ms 32792 KB Output is correct
4 Correct 92 ms 26864 KB Output is correct
5 Correct 89 ms 25024 KB Output is correct
6 Correct 117 ms 31276 KB Output is correct
7 Correct 98 ms 20496 KB Output is correct
8 Correct 122 ms 24148 KB Output is correct
9 Correct 89 ms 15632 KB Output is correct
10 Correct 89 ms 17708 KB Output is correct
11 Runtime error 29 ms 19024 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Runtime error 2 ms 604 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 28280 KB Output is correct
2 Correct 111 ms 28272 KB Output is correct
3 Correct 114 ms 28316 KB Output is correct
4 Correct 131 ms 28788 KB Output is correct
5 Correct 107 ms 28492 KB Output is correct
6 Correct 166 ms 46852 KB Output is correct
7 Correct 168 ms 40740 KB Output is correct
8 Correct 168 ms 37480 KB Output is correct
9 Correct 130 ms 34672 KB Output is correct
10 Correct 109 ms 20764 KB Output is correct
11 Correct 110 ms 26224 KB Output is correct
12 Correct 96 ms 16164 KB Output is correct
13 Correct 98 ms 15288 KB Output is correct
14 Runtime error 39 ms 19796 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 420 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 1 ms 732 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Runtime error 2 ms 604 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 28204 KB Output is correct
2 Correct 126 ms 28680 KB Output is correct
3 Correct 117 ms 27904 KB Output is correct
4 Correct 120 ms 23748 KB Output is correct
5 Correct 79 ms 19328 KB Output is correct
6 Correct 65 ms 17372 KB Output is correct
7 Correct 65 ms 16372 KB Output is correct
8 Correct 54 ms 14992 KB Output is correct
9 Correct 57 ms 14480 KB Output is correct
10 Correct 48 ms 14220 KB Output is correct
11 Correct 44 ms 13392 KB Output is correct
12 Correct 48 ms 12884 KB Output is correct
13 Correct 47 ms 12880 KB Output is correct
14 Correct 56 ms 16580 KB Output is correct
15 Correct 167 ms 39432 KB Output is correct
16 Correct 140 ms 35444 KB Output is correct
17 Correct 129 ms 35516 KB Output is correct
18 Correct 136 ms 32112 KB Output is correct
19 Correct 96 ms 23048 KB Output is correct
20 Correct 95 ms 18264 KB Output is correct
21 Correct 122 ms 15660 KB Output is correct
22 Runtime error 44 ms 20820 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -