oj.uz

Submission #1057856

# Submission time Handle Problem Language Result Execution time Memory
1057856 2024-08-14T06:52:06 Z caterpillow Duathlon (APIO18_duathlon) C++17
31 / 100
 60 ms 36988 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] = size(adj[u]) >= 2;
                    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]) {
            dbg(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++;
    }

    // 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 344 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 344 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 32 ms 18776 KB Output is correct
2 Correct 34 ms 18776 KB Output is correct
3 Correct 49 ms 24092 KB Output is correct
4 Correct 35 ms 22276 KB Output is correct
5 Correct 40 ms 19860 KB Output is correct
6 Correct 47 ms 24588 KB Output is correct
7 Correct 47 ms 23556 KB Output is correct
8 Correct 45 ms 24208 KB Output is correct
9 Correct 47 ms 22532 KB Output is correct
10 Correct 40 ms 22016 KB Output is correct
11 Correct 34 ms 17352 KB Output is correct
12 Correct 35 ms 18180 KB Output is correct
13 Correct 30 ms 16556 KB Output is correct
14 Correct 30 ms 16132 KB Output is correct
15 Correct 21 ms 13568 KB Output is correct
16 Correct 23 ms 13324 KB Output is correct
17 Correct 3 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 4420 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 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 720 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 0 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 46 ms 26364 KB Output is correct
2 Correct 48 ms 26424 KB Output is correct
3 Correct 51 ms 27648 KB Output is correct
4 Correct 49 ms 27644 KB Output is correct
5 Correct 46 ms 26368 KB Output is correct
6 Correct 60 ms 36988 KB Output is correct
7 Correct 57 ms 33280 KB Output is correct
8 Correct 57 ms 32428 KB Output is correct
9 Correct 55 ms 31228 KB Output is correct
10 Correct 49 ms 28156 KB Output is correct
11 Correct 46 ms 27388 KB Output is correct
12 Correct 46 ms 26676 KB Output is correct
13 Correct 50 ms 26112 KB Output is correct
14 Correct 46 ms 26112 KB Output is correct
15 Correct 41 ms 22272 KB Output is correct
16 Correct 30 ms 15360 KB Output is correct
17 Correct 40 ms 23012 KB Output is correct
18 Correct 34 ms 22968 KB Output is correct
19 Correct 36 ms 23008 KB Output is correct
20 Correct 38 ms 23296 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 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 46 ms 25084 KB Output is correct
2 Correct 52 ms 27292 KB Output is correct
3 Incorrect 49 ms 26360 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 344 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 344 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 -