oj.uz

답안 #900502

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
900502 2024-01-08T11:32:55 Z shmax 철인 이종 경기 (APIO18_duathlon) C++14
31 / 100
 161 ms 70044 KB 
/*
 * powered by ANDRIY POPYK
 * in honor of MYSELF and SEGMENT DECOMPOSITION and N^(log(N)) and (Harry Potter and the Methods of Rationality) and Monkie D. Luffy
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt")

using namespace std;
using namespace __gnu_pbds;
#define int long long
#define float long double
#define elif else if
#define endl "\n"
#define mod 1000000007
#define pi acos(-1)
#define eps 0.000000001
#define inf 1000'000'000'000'000'000LL
#define FIXED(a) cout << fixed << setprecision(a)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define time_init auto start = std::chrono::high_resolution_clock::now()
#define time_report                                       \
    auto end = std::chrono::high_resolution_clock::now(); \
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << endl
#define debug(x) \
    { cerr << #x << " = " << x << endl; }
#define len(x) (int) x.size()
#define sqr(x) ((x) * (x))
#define cube(x) ((x) * (x) * (x))
#define bit(x, i) (((x) >> (i)) & 1)
#define set_bit(x, i) ((x) | (1LL << (i)))
#define clear_bit(x, i) ((x) & (~(1LL << (i))))
#define toggle_bit(x, i) ((x) ^ (1LL << (i)))
#define low_bit(x) ((x) & (-(x)))
#define count_bit(x) __builtin_popcountll(x)
#define srt(x) sort(all(x))
#define rsrt(x) sort(rall(x))
#define mp make_pair
#define maxel(x) (*max_element(all(x)))
#define minel(x) (*min_element(all(x)))
#define maxelpos(x) (max_element(all(x)) - x.begin())
#define minelpos(x) (min_element(all(x)) - x.begin())
#define sum(x) (accumulate(all(x), 0LL))
#define product(x) (accumulate(all(x), 1LL, multiplies<int>()))
#define gcd __gcd
#define lcm(a, b) ((a) / gcd(a, b) * (b))
#define rev(x) (reverse(all(x)))
#define shift_left(x, k) (rotate(x.begin(), x.begin() + k, x.end()))
#define shift_right(x, k) (rotate(x.rbegin(), x.rbegin() + k, x.rend()))
#define is_sorted(x) (is_sorted_until(all(x)) == x.end())
#define is_even(x) (((x) &1) == 0)
#define is_odd(x) (((x) &1) == 1)
#define pow2(x) (1LL << (x))

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using matrix = vector<vector<T>>;
template<typename T>
using graph = vector<vector<T>>;
using hashmap = gp_hash_table<int, int, custom_hash>;

template<typename T>
vector<T> vect(int n, T val) {
    return vector<T>(n, val);
}

template<typename T>
vector<vector<T>> vect(int n, int m, T val) {
    return vector<vector<T>>(n, vector<T>(m, val));
}

template<typename T>
vector<vector<vector<T>>> vect(int n, int m, int k, T val) {
    return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, val)));
}

template<typename T>
vector<vector<vector<vector<T>>>> vect(int n, int m, int k, int l, T val) {
    return vector<vector<vector<vector<T>>>>(n, vector<vector<vector<T>>>(m, vector<vector<T>>(k, vector<T>(l, val))));
}

template<typename T>
matrix<T> new_matrix(int n, int m, T val) {
    return matrix<T>(n, vector<T>(m, val));
}

template<typename T>
graph<T> new_graph(int n) {
    return graph<T>(n);
}

template<class T, class S>
inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}

template<class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}

using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
template<typename T>
using vec = vector<T>;

using pII = pair<int, int>;
template<typename T>
using enumerated = pair<T, int>;

struct BlockCutTree {
public:
    graph<int> g;
    int timer, n;
    vec<int> fup, tin;
    vec<bool> used;
    vec<vec<pII>> edge_components;
    vec<int> components;
    vec<int> comp_vertices;
    vec<int> cut_points;
    vec<bool> is_cut_point;
    stack<pII> buffer;
    int component_cnt;

    void dfs(int v, int p) {
        tin[v] = fup[v] = timer++;
        used[v] = true;
        bool is_cut = false;
        int child_cnt = 0;
        for (auto u: g[v]) {
            if (u == p)
                continue;
            if (!used[u]) {
                child_cnt++;
                buffer.emplace(v, u);
                dfs(u, v);
                if (fup[u] >= tin[v]) {
                    is_cut = true;
                    edge_components.emplace_back();
                    while (true) {
                        auto [a, b] = buffer.top();
                        buffer.pop();
                        edge_components.back().emplace_back(a, b);
                        if (a == v && b == u) {
                            break;
                        }
                    }
                }
                chmin(fup[v], fup[u]);
            } else {
                chmin(fup[v], tin[u]);
                if (tin[u] < tin[v]) {
                    buffer.emplace(v, u);
                }
            }
        }


        if (p == -1) {
            is_cut = child_cnt > 1;
        }
        if(p == -1 and child_cnt == 0){
            is_cut = true;
        }
        if (is_cut) {
            cut_points.push_back(v);
            is_cut_point[v] = true;
        }
    }

    void build_components() {
        for (int i = 0; i < n; ++i) {
            if (!used[i]) {
                dfs(i, -1);
            }
        }
        components = vec<int>(n);
        component_cnt = 0;
        for (auto cp: cut_points) {
            components[cp] = component_cnt++;
        }
        for (auto &ec: edge_components) {
            for (auto [u, v]: ec) {
                if (!is_cut_point[u])
                    components[u] = component_cnt;
                if (!is_cut_point[v])
                    components[v] = component_cnt;
            }
//            if (was)
            component_cnt++;
        }

        comp_vertices.resize(component_cnt);
        for (int i = 0; i < n; ++i) {
            comp_vertices[components[i]]++;
        }
    }

    graph<int> bc_tree;

    void build_tree() {
        bc_tree = graph<int>(component_cnt);
        set<pair<int, int>> bc_tree_edges;
        int id = len(cut_points) - 1;
        for (const auto &eg: edge_components) {
            id++;
            for (auto [u, v]: eg) {
                if (is_cut_point[u]) {
//                    bc_tree_edges[components[u]].insert(id);
//                    bc_tree_edges[id].insert(components[u]);
                    int v_u = components[u];
                    int v_v = id;
                    if (v_u > v_v) {
                        swap(v_u, v_v);
                    }
                    bc_tree_edges.emplace(v_u, v_v);
                }
                if (is_cut_point[v]) {
                    int v_u = components[v];
                    int v_v = id;
                    if (v_u > v_v) {
                        swap(v_u, v_v);
                    }
                    bc_tree_edges.emplace(v_u, v_v);
                }
            }
        }
//        for (int i = 0; i < component_cnt; ++i) {
//            for (auto to: bc_tree_edges[i]) {
//                bc_tree[i].push_back(to);
//            }
//        }
        for (auto [u, v]: bc_tree_edges) {
            bc_tree[u].push_back(v);
            bc_tree[v].push_back(u);
        }
    }

    BlockCutTree(graph<int> &g) : g(g) {
        n = len(g);
        timer = 0;
        fup = tin = vec<int>(n);
        used = vec<bool>(n);
        is_cut_point = vec<bool>(n);
    }

    void print() {
        set<pII> edges;
        for (int i = 0; i < component_cnt; ++i) {
            for (auto to: bc_tree[i]) {
                if (edges.count({i, to}) or edges.count({to, i})) {
                    continue;
                }
                edges.emplace(i, to);
            }
        }
        cout << len(edges) << endl;
        for (auto [u, v]: edges) {
            cout << u + 1 << " " << v + 1 << endl;
        }
    }
};


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    i64 n, m;
    cin >> n >> m;
    graph<int> g(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v, --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

//    int all = 0;
//    vec<int> sizes(n, 0);
//    vec<bool> was(n, false);

/*
    function<void(int, int)> dfs = [&](int v, int p) {
        if (was[v]) return;
        was[v] = true;
        sizes[v] = 1;
        for (auto u: g[v]) {
            if (u == p) continue;
            dfs(u, v);
            sizes[v] += sizes[u];
        }
        int top = ttn - sizes[v];
        all += top * (sizes[v] - 1) * 2;

        for (auto u: g[v]) {
            if (u == p) continue;
            int tn = sizes[v] - 1 - sizes[u];
            all += tn * sizes[u];
        }
    };
*/
    BlockCutTree bct(g);
    bct.build_components();
    bct.build_tree();
//    bct.print();
//    cout << endl;
    i64 all = 0;
    int dn = len(bct.bc_tree);
    vec<int> sizes(dn, 0);
    vec<bool> was(dn, false);

    function<int(int, int)> calc_cur_size = [&](int v, int p) {
        int sum = bct.comp_vertices[v];
        for (auto u: bct.bc_tree[v]) {
            if (u != p)
                sum += calc_cur_size(u, v);
        }
        return sum;
    };

    int ttn = n;
    function<void(int, int)> dfs = [&](int v, int p) {
        if (was[v]) return;
        was[v] = true;
        sizes[v] = bct.comp_vertices[v];
        for (auto u: bct.bc_tree[v]) {
            if (u == p)
                continue;
            dfs(u, v);
            sizes[v] += sizes[u];
        }
        if (bct.comp_vertices[v] >= 3) {
            int tc = bct.comp_vertices[v];
            all += tc * (tc - 1) * (tc - 2);
        }
        if (bct.comp_vertices[v] >= 2) {
            int tc = bct.comp_vertices[v];
            int top = ttn - sizes[v];
            all += tc * (tc - 1) * top * 2;
        }
        int top = ttn - sizes[v];
        int tc = bct.comp_vertices[v];


        for (auto u: bct.bc_tree[v]) {
            if (u == p)
                continue;
            all += top * tc * sizes[u] * 2;
            all += tc * (tc - 1) * sizes[u] * 2;
            all += bct.comp_vertices[u] * (bct.comp_vertices[u] - 1) * tc;
            int dc = sizes[v] - sizes[u] - tc;
            all += tc * dc * sizes[u];
        }
    };
    for (int i = 0; i < dn; i++) {
        if (!was[i]) {
            ttn = calc_cur_size(i, -1);
            dfs(i, -1);
        }
    }
    cout << all << endl;

}

Compilation message

count_triplets.cpp: In member function 'void BlockCutTree::dfs(long long int, long long int)':
count_triplets.cpp:174:30: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  174 |                         auto [a, b] = buffer.top();
      |                              ^
count_triplets.cpp: In member function 'void BlockCutTree::build_components()':
count_triplets.cpp:216:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  216 |             for (auto [u, v]: ec) {
      |                       ^
count_triplets.cpp: In member function 'void BlockCutTree::build_tree()':
count_triplets.cpp:240:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  240 |             for (auto [u, v]: eg) {
      |                       ^
count_triplets.cpp:266:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  266 |         for (auto [u, v]: bc_tree_edges) {
      |                   ^
count_triplets.cpp: In member function 'void BlockCutTree::print()':
count_triplets.cpp:291:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  291 |         for (auto [u, v]: edges) {
      |                   ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 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 1 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 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 1 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 30884 KB Output is correct
2 Correct 60 ms 30924 KB Output is correct
3 Correct 91 ms 42692 KB Output is correct
4 Correct 81 ms 33168 KB Output is correct
5 Correct 72 ms 33360 KB Output is correct
6 Correct 105 ms 45764 KB Output is correct
7 Correct 93 ms 38152 KB Output is correct
8 Correct 97 ms 42124 KB Output is correct
9 Correct 93 ms 35708 KB Output is correct
10 Correct 109 ms 34568 KB Output is correct
11 Correct 67 ms 24800 KB Output is correct
12 Correct 65 ms 26112 KB Output is correct
13 Correct 59 ms 23816 KB Output is correct
14 Correct 73 ms 23912 KB Output is correct
15 Correct 38 ms 19976 KB Output is correct
16 Correct 64 ms 20372 KB Output is correct
17 Correct 7 ms 12240 KB Output is correct
18 Correct 7 ms 12240 KB Output is correct
19 Correct 8 ms 12236 KB Output is correct
20 Correct 10 ms 12236 KB Output is correct
21 Correct 9 ms 12240 KB Output is correct
22 Correct 10 ms 12240 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 860 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 2 ms 1112 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1 ms 860 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 604 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 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 124 ms 39956 KB Output is correct
2 Correct 124 ms 39936 KB Output is correct
3 Correct 125 ms 39832 KB Output is correct
4 Correct 117 ms 40100 KB Output is correct
5 Correct 105 ms 40268 KB Output is correct
6 Correct 161 ms 70044 KB Output is correct
7 Correct 129 ms 51708 KB Output is correct
8 Correct 123 ms 49164 KB Output is correct
9 Correct 131 ms 46252 KB Output is correct
10 Correct 114 ms 39712 KB Output is correct
11 Correct 121 ms 39680 KB Output is correct
12 Correct 97 ms 39936 KB Output is correct
13 Correct 99 ms 39732 KB Output is correct
14 Correct 85 ms 36492 KB Output is correct
15 Correct 88 ms 34120 KB Output is correct
16 Correct 44 ms 23680 KB Output is correct
17 Correct 70 ms 36084 KB Output is correct
18 Correct 74 ms 35956 KB Output is correct
19 Correct 71 ms 35628 KB Output is correct
20 Correct 85 ms 36144 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 860 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 142 ms 39792 KB Output is correct
2 Correct 118 ms 41044 KB Output is correct
3 Incorrect 108 ms 38084 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 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 1 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 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 1 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -