oj.uz

Submission #1057920

# Submission time Handle Problem Language Result Execution time Memory
1057920 2024-08-14T07:20:53 Z caterpillow Duathlon (APIO18_duathlon) C++17
31 / 100
 77 ms 50204 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<vt<int>> rcomp;

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] - 1) * (sub[v] - 1) * 2 + (sz[u] - 1) * (sz[u] - 2) * (sub[v] - 1) * 2;
    }

    // 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("\n", rcomp[u]);
    dbg(ans, sub[u], pairs[u], sz[u]);
}

/*

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
        - case 1: includes the shared node
        - case 2: exclues shared node
    - 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({});
            rcomp.pb({i});
        }
    }
    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]);
            }
        }
        rcomp.pb(comp);
        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:225:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  225 | 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 56 ms 19228 KB Output is correct
2 Correct 33 ms 19148 KB Output is correct
3 Correct 47 ms 30732 KB Output is correct
4 Correct 39 ms 24068 KB Output is correct
5 Correct 39 ms 24220 KB Output is correct
6 Correct 50 ms 30648 KB Output is correct
7 Correct 61 ms 29700 KB Output is correct
8 Correct 53 ms 30352 KB Output is correct
9 Correct 64 ms 28428 KB Output is correct
10 Correct 71 ms 26080 KB Output is correct
11 Correct 38 ms 23044 KB Output is correct
12 Correct 42 ms 22380 KB Output is correct
13 Correct 36 ms 22300 KB Output is correct
14 Correct 37 ms 22020 KB Output is correct
15 Correct 28 ms 20488 KB Output is correct
16 Correct 47 ms 20236 KB Output is correct
17 Correct 2 ms 4320 KB Output is correct
18 Correct 3 ms 4332 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 4380 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 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 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 648 KB Output is correct
14 Correct 0 ms 604 KB Output is correct
15 Correct 0 ms 604 KB Output is correct
16 Correct 0 ms 600 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 1 ms 604 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 35360 KB Output is correct
2 Correct 56 ms 33532 KB Output is correct
3 Correct 54 ms 34556 KB Output is correct
4 Correct 55 ms 34304 KB Output is correct
5 Correct 55 ms 34572 KB Output is correct
6 Correct 69 ms 50204 KB Output is correct
7 Correct 63 ms 41848 KB Output is correct
8 Correct 67 ms 43508 KB Output is correct
9 Correct 65 ms 42172 KB Output is correct
10 Correct 55 ms 33276 KB Output is correct
11 Correct 56 ms 35072 KB Output is correct
12 Correct 54 ms 36104 KB Output is correct
13 Correct 55 ms 33160 KB Output is correct
14 Correct 52 ms 33288 KB Output is correct
15 Correct 52 ms 33792 KB Output is correct
16 Correct 32 ms 21764 KB Output is correct
17 Correct 35 ms 27704 KB Output is correct
18 Correct 35 ms 27904 KB Output is correct
19 Correct 35 ms 27580 KB Output is correct
20 Correct 36 ms 28168 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 1 ms 600 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 58 ms 33024 KB Output is correct
2 Correct 61 ms 37416 KB Output is correct
3 Incorrect 56 ms 31744 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 -