oj.uz

Submission #630649

# Submission time Handle Problem Language Result Execution time Memory
630649 2022-08-16T19:53:54 Z SorahISA Duathlon (APIO18_duathlon) C++17
0 / 100
 114 ms 29740 KB 
#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define double long double
using pii = pair<int, int>;
template <typename T>
using Prior = std::priority_queue<T>;
template <typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;

// #define X first
// #define Y second
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

#ifdef local
#define fastIO() void()
#define debug(...) \
    _color.eb("\u001b[31m"),\
    cerr << _color.back() << "At [" << __FUNCTION__ << "], line " << __LINE__ << ": ",\
    cerr << "(" << #__VA_ARGS__ << ") = ", _do(__VA_ARGS__),\
    _color.pb(),\
    cerr << _color.back()
deque<string> _color{"\u001b[0m"};

template <typename T> concept is_string = is_same_v<T, string&> or is_same_v<T, const string&>;
template <typename T> concept is_iterable = requires (T _t) {begin(_t);};

template <typename T> inline void _print_err(T &&_t) {cerr << _t;}
template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>) {
    string _tmp_color = _color.back();
    ++_tmp_color[3], _color.eb(_tmp_color);
    cerr << _color.back() << "[";
    for (bool _first = true; auto &_x : _t) {
        if (!_first) cerr << ", ";
        _print_err(_x), _first = false;
    }
    cerr << "]" << (_color.pb(), _color.back());
}

template <typename T, typename U> ostream& operator << (ostream &os, pair<T, U> &_tu) {
    string _tmp_color = _color.back();
    ++_tmp_color[3], _color.eb(_tmp_color);
    cerr << _color.back() << "(";
    _print_err(_tu.first), cerr << ", ", _print_err(_tu.second);
    cerr << ")" << (_color.pb(), _color.back());
    return os;
}

template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &) {
    cerr << ")" << (_color.pb(), _color.back());
}

template <size_t I = 0, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(tuple<U...> &_t) {
    if (!I) {
        string _tmp_color = _color.back();
        ++_tmp_color[3], _color.eb(_tmp_color);
        cerr << _color.back();
    }
    cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}

template <typename T> inline void _do(T &&_t) {_print_err(_t), cerr << "\n";}
template <typename T, typename ...U> inline void _do(T &&_t, U &&..._u) {_print_err(_t), cerr << ", ", _do(_u...);}
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

inline int getRand(int L, int R) {
    if (L > R) swap(L, R);
    return (int)(rng() % ((uint64_t)R - L + 1) + L);
}

template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}

const int maxn = 1E5 + 5;

vector<int> adj[maxn], dfn, low;
vector<int> bct[2*maxn];
deque<int> stk;

void Tarjan(int now, int &tok_dfn, int &tok_bcc) {
    dfn[now] = low[now] = tok_dfn++;
    stk.eb(now);
    int cnt_ch = 0;
    for (int x : adj[now]) {
        if (!~dfn[x]) {
            ++cnt_ch;
            Tarjan(x, tok_dfn, tok_bcc);
            chmin(low[now], low[x]);
            // debug(now, x, dfn[now], low[x], stk);
            if (low[x] >= dfn[now]) {
                int p;
                while ((p = stk.back()) != x) {
                    bct[p].eb(tok_bcc), bct[tok_bcc].eb(p), stk.pb();
                }
                bct[p].eb(tok_bcc), bct[tok_bcc].eb(p), stk.pb();
                bct[now].eb(tok_bcc), bct[tok_bcc].eb(now);
                ++tok_bcc;
            }
        }
        chmin(low[now], dfn[x]);
    }
    // debug(now, dfn[now], low[now]);
}

void solve() {
    int N, M; cin >> N >> M;
    
    for (int i = 0, u, v; i < M; ++i) {
        cin >> u >> v, --u, --v;
        adj[u].eb(v), adj[v].eb(u);
    }
    
    dfn.assign(N, -1), low.resize(N);
    
    int tok_bcc = N;
    for (int i = 0, tok_dfn = 0; i < N; ++i) {
        if (!~dfn[i]) stk.clear(), Tarjan(i, tok_dfn, tok_bcc);
    }
    
    for (int i = N; i < tok_bcc; ++i) debug(i, bct[i]);
    
    /// calculate answer in Block-Cut Tree ///
    
    vector<int> vis(tok_bcc, 0), sz(tok_bcc, 0), sub(tok_bcc, 0);
    
    /// size of ap = 1; size of bcc = (# of vertex) - (# of ap) ///
    for (int i = 0; i < N; ++i) ++sz[SZ(bct[i]) == 1 ? bct[i][0] : i];
    
    int ans = 0;
    for (int i = 0; i < N; ++i) {
        if (vis[i]) continue;
        
        auto get_sz_ = [&](auto &&get_sz, int now, int fa) -> void {
            vis[now] = true, sub[now] = sz[now];
            for (int x : bct[now]) {
                if (x == fa) continue;
                get_sz(get_sz, x, now), sub[now] += sub[x];
            }
            debug(now, fa, sz[now], sub[now], bct[now]);
        };
        get_sz_(get_sz_, i, -1);
        
        int sz_all = sub[i];
        
        auto dfs_ = [&](auto &&dfs, int now, int fa) -> void {
            for (int x : bct[now]) if (x != fa) dfs(dfs, x, now);
            
            // debug("before"s, now, ans);
            /// pick (s, c, f) in this {bcc `now` \ ap} ///
            ans += sz[now] * (sz[now] - 1) * (sz[now] - 2);
            /// pick (s, c) in this {bcc `now` \ ap}; (f) in other place (*2 because symmetric) ///
            ans += sz[now] * (sz[now] - 1) * (sz_all - sz[now]) * 2;
            /// pick (s) in child `fa`; (c) in this ap or {bcc `now` \ ap}; (f) in other children ///
            ans += (sz_all - sub[now]) * sz[now] * (sub[now] - sz[now]);
            for (int x : bct[now]) {
                /// pick (s) in child `x`; (c) in this ap or {bcc `now` \ ap}; (f) in other children ///
                if (x != fa) ans += sub[x] * sz[now] * (sz_all - sz[now] - sub[x]);
                /// pick (s) in {bcc `x` \ `now`}; (c) in this ap; (f) in child `x` (*2 because symmetric) ///
                ans += (SZ(bct[x]) - 1) * (now < N and SZ(bct[now]) > 1) * (sub[x] - 1) * 2;
                /// minus f-s-c case (*2 because symmetric) ///
                
            }
            // debug(" after"s, now, ans);
        };
        dfs_(dfs_, i, -1);
    }
    cout << ans << "\n";
}

int32_t main() {
    fastIO();
    
    int t = 1; // cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        // cout << "Case #" << _ << ": ";
        solve();
    }
    
    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 29588 KB Output is correct
2 Correct 79 ms 29740 KB Output is correct
3 Incorrect 103 ms 26636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 24408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 24560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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