oj.uz

Submission #1057885

# Submission time Handle Problem Language Result Execution time Memory
1057885 2024-08-14T07:08:31 Z caterpillow Duathlon (APIO18_duathlon) C++17
31 / 100
 70 ms 35476 KB 
#include <bits/stdc++.h>

using namespace std;

using db = long double;
using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

template<typename... Args> // tuples
ostream& operator<<(ostream& os, tuple<Args...> t) { 
    apply([&](Args... args) { string dlm = "{"; ((os << dlm << args, dlm = ", "), ...); }, t);
    return os << "}";
}

template<typename T, typename V> // pairs
ostream& operator<<(ostream& os, pair<T, V> p) { return os << "{" << p.f << ", " << p.s << "}"; }

template<class T, class = decltype(begin(declval<T>()))> // iterables
typename enable_if<!is_same<T, string>::value, ostream&>::type operator<<(ostream& os, const T& v) {
    string dlm = "{";
    for (auto i : v) os << dlm << i, dlm = ", ";
    return os << "}";  
}

template <typename T, typename... V>
void printer(string pfx, const char *names, T&& head, V&& ...tail) {
    int i = 0;
    while (names[i] && names[i] != ',') i++;
    constexpr bool is_str = is_same_v<decay_t<T>, const char*>;
    if (is_str) cerr << " " << head;
    else cerr << pfx, cerr.write(names, i) << " = " << head; 
    if constexpr (sizeof...(tail)) printer(is_str ? "" : ",", names + i + 1, tail...);
    else cerr << endl;
}

#ifdef LOCAL
#define dbg(...) printer(to_string(__LINE__) + ": ", #__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif

/*

consider when its *not* possible to find a path between three nodes a, b and c
obv, they need to be in the same connected component
clearly, you can go from a to b, and you can also go from b to c
we just need to account for the condition that you cant use the same node twice

consider the block cut tree
a triple is good as long as a, b, and c belong on the same path, in that order

do subtree dp, counting the # of paths with it as their lca
be very careful, since neighbours in the block cut tree share a node which we must not overcount
when counting for some lca, we exclude the shared node with children

cases:
    - we can take a pair from some subtree (excluding shared) and one from another
    - we can take a node each from two subtrees (excluding shared) and one in the root
    - we can take a pair from a subtree (excluding shared) and one from the root (excluding shared)

    additionally, if the root has sufficient nodes
    - we can take two nodes from the root and some node (excluding shared) in a subtree
    - we can take three nodes from the root

we need to track in our dp:
    - how many unique child nodes there are in the subtree (careful overcounting articulation points)
        - this is size of yourself + dp value of children - # of children
    - how many ordered pairs there are in the subtree that lead to the root EXCLUDING the shared node with the parent
        - sum of pairs of children, and (sum of child sizes excluding shared) * (size of root - 1), and (size - 1) * (size - 2)

sum over all roots

*/

struct BCC {
    int n, t; 
    vt<vt<int>> adj;
    vt<int> tin, low, stk;
    vt<bool> is_art;
    vt<vt<int>> comps;

    void init(int _n) {
        n = _n;
        t = 0;
        adj.resize(n);
        tin = low = vt<int>(n);
        is_art.resize(n);
    }

    void ae(int u, int v) {
        adj[u].pb(v);
        adj[v].pb(u);
    }

    void dfs(int u) {
        tin[u] = low[u] = ++t;
        stk.pb(u);
        for (int v : adj[u]) {
            if (tin[v]) low[u] = min(low[u], tin[v]);
            else {
                dfs(v);
                low[u] = min(low[u], low[v]);
                if (low[v] == tin[u]) {
                    is_art[u] = (u != stk[0]) || tin[v] > tin[u] + 1;
                    comps.pb({u});
                    do {
                        comps.back().pb(stk.back());
                        stk.pop_back();
                    } while (stk.back() != u);
                }
            }
        }
    }

    void gen() {
        F0R (i, n) if (!tin[i]) dfs(i);
        for (auto c : comps) dbg(c);
    }
};

int n;
BCC bcc;
vt<vt<int>> adj;
vt<int> id;
vt<ll> sz;

vt<ll> sub, pairs;
vt<bool> seen;
ll ans = 0;

void dfs(int u, int p) {
    seen[u] = true;

    for (int v : adj[u]) if (v != p) dfs(v, u);

    // do the first three cases, since they are shared

    ll available = 0; // # of nodes in children that arent part of the root
    for (int v : adj[u]) {
        if (v == p) continue;
        available += sub[v] - 1; // exclude the shared node
    }

    // case 1
    for (int v : adj[u]) {
        if (v == p) continue;
        ans += pairs[v] * (available - (sub[v] - 1)) * 2;        
    }

    // case 2
    for (int v : adj[u]) {
        if (v == p) continue;
        ans += sz[u] * (sub[v] - 1) * (available - (sub[v] - 1));
    }

    // case 3
    for (int v : adj[u]) {
        if (v == p) continue;
        ans += (sz[u] - 1) * pairs[v] * 2;
    }

    // case 4
    for (int v : adj[u]) {
        if (v == p) continue;
        ans += sz[u] * (sz[u] - 1) * (sub[v] - 1);
    }

    // case 5
    ans += sz[u] * (sz[u] - 1) * (sz[u] - 2);

    // calc dp values
    sub[u] = available + sz[u];

    pairs[u] = available * (sz[u] - 1) + (sz[u] - 1) * (sz[u] - 2);
    for (int v : adj[u]) {
        if (v == p) continue;
        pairs[u] += pairs[v];
    }
    dbg(u, ans, sub[u], pairs[u], sz[u]);
    dbg(adj[u], p);
}

/*

do subtree dp, counting the # of paths with it as their lca
be very careful, since neighbours in the block cut tree share a node which we must not overcount
when counting for some lca, we exclude the shared node with children

cases:
    - we can take a pair from some subtree (excluding shared) and one from another
    - we can take a node each from two subtrees (excluding shared) and one in the root
    - we can take a pair from a subtree (excluding shared) and one from the root (excluding shared)

    additionally, if the root has sufficient nodes
    - we can take two nodes from the root and some node (excluding shared) in a subtree (i think)
    - we can take three nodes from the root (any)

we need to track in our dp:
    - how many unique child nodes there are in the subtree (careful overcounting articulation points)
        - this is size of yourself + dp value of children - # of children
    - how many ordered pairs there are in the subtree that lead to the root EXCLUDING the shared node with the parent
        - sum of pairs of children, and (sum of child sizes excluding shared) * (size of root - 1), and (size - 1) * (size - 2)

sum over all roots

*/

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int _n; cin >> _n;
    bcc.init(_n);
    int m; cin >> m;
    F0R (i, m) {
        int u, v; cin >> u >> v; u--, v--;
        bcc.ae(u, v);
    }
    bcc.gen();

    // build block cut tree
    id.resize(_n);
    F0R (i, _n) {
        if (bcc.is_art[i]) {
            id[i] = n++;
            sz.pb(1);
            adj.pb({});
        }
    }
    for (vt<int>& comp : bcc.comps) {
        adj.pb({});
        sz.pb(size(comp));
        for (int u : comp) {
            if (bcc.is_art[u]) {
                adj[id[u]].pb(n);
                adj[n].pb(id[u]);
            }
        }
        n++;
    }
    dbg(bcc.is_art);

    // start counting
    dbg(n);
    sub = pairs = vt<ll>(n);

    seen.resize(n);
    F0R (i, n) {
        if (!seen[i]) dfs(i, -1);
    }

    cout << ans << endl;
}

Compilation message

count_triplets.cpp:222:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  222 | main() {
      | ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 18764 KB Output is correct
2 Correct 30 ms 18776 KB Output is correct
3 Correct 43 ms 23556 KB Output is correct
4 Correct 36 ms 21004 KB Output is correct
5 Correct 35 ms 19080 KB Output is correct
6 Correct 44 ms 23300 KB Output is correct
7 Correct 53 ms 22268 KB Output is correct
8 Correct 46 ms 23048 KB Output is correct
9 Correct 40 ms 21252 KB Output is correct
10 Correct 43 ms 20228 KB Output is correct
11 Correct 32 ms 17412 KB Output is correct
12 Correct 32 ms 17268 KB Output is correct
13 Correct 30 ms 17140 KB Output is correct
14 Correct 30 ms 16384 KB Output is correct
15 Correct 25 ms 15616 KB Output is correct
16 Correct 23 ms 15116 KB Output is correct
17 Correct 2 ms 4320 KB Output is correct
18 Correct 2 ms 4324 KB Output is correct
19 Correct 2 ms 4320 KB Output is correct
20 Correct 2 ms 4324 KB Output is correct
21 Correct 2 ms 4316 KB Output is correct
22 Correct 2 ms 4316 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 0 ms 604 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 0 ms 604 KB Output is correct
18 Correct 0 ms 604 KB Output is correct
19 Correct 0 ms 604 KB Output is correct
20 Correct 0 ms 604 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 25480 KB Output is correct
2 Correct 56 ms 25856 KB Output is correct
3 Correct 47 ms 25596 KB Output is correct
4 Correct 47 ms 25852 KB Output is correct
5 Correct 46 ms 25340 KB Output is correct
6 Correct 57 ms 35476 KB Output is correct
7 Correct 70 ms 31744 KB Output is correct
8 Correct 56 ms 30716 KB Output is correct
9 Correct 56 ms 28676 KB Output is correct
10 Correct 46 ms 26620 KB Output is correct
11 Correct 45 ms 25084 KB Output is correct
12 Correct 50 ms 25344 KB Output is correct
13 Correct 51 ms 26112 KB Output is correct
14 Correct 53 ms 24800 KB Output is correct
15 Correct 46 ms 23552 KB Output is correct
16 Correct 25 ms 16392 KB Output is correct
17 Correct 30 ms 21736 KB Output is correct
18 Correct 30 ms 21508 KB Output is correct
19 Correct 31 ms 21640 KB Output is correct
20 Correct 30 ms 21596 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 25796 KB Output is correct
2 Correct 48 ms 26364 KB Output is correct
3 Incorrect 50 ms 23500 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -