답안 #1057920

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1057920	2024-08-14T07:20:53 Z	caterpillow	철인 이종 경기 (APIO18_duathlon)	C++17	31 / 100	77 ms	50204 KB

count_triplets

#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

#	결과	메모리	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Incorrect	348 KB	Output isn't correct
8	Halted	0 KB	-

Subtask #2
0 / 11.0

#	결과	메모리	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Incorrect	348 KB	Output isn't correct
8	Halted	0 KB	-

Subtask #3
8.0 / 8.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	메모리	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Incorrect	348 KB	Output isn't correct
8	Halted	0 KB	-

Subtask #9
0 / 10.0

#	결과	메모리	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Incorrect	348 KB	Output isn't correct
8	Halted	0 KB	-