oj.uz

Submission #137941

# Submission time Handle Problem Language Result Execution time Memory
137941 2019-07-28T15:06:55 Z darkkcyan ICC (CEOI16_icc) C++14
100 / 100
 147 ms 664 KB 
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
using namespace std::placeholders;

#define llong long long 
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define all(x) x.begin(), x.end()
#define rand __rand
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64
template<class T = int> T rand(T range = numeric_limits<T>::max()) {
    return (T)(rng() % range);
}

///////////////////////////////////////////////////////////////////////////////////////////
#define maxn 111

// int query_cnt = 0;
template<class container>
int query(const container& a, const container& b) {
    // ++query_cnt;
    // clog << "query: " << query_cnt << ": " << endl;
    // clog << "{"; for (auto i: a) clog << i << ", "; clog << "} " << endl;
    // clog << "{"; for (auto i: b) clog << i << ", "; clog << "} " << endl;
    int cpy_a[len(a)], cpy_b[len(b)];
    copy(a.begin(), a.end(), cpy_a);
    copy(b.begin(), b.end(), cpy_b);
    return query(len(a), len(b), cpy_a, cpy_b);
}

namespace solution_100_points { void run(int n); }
namespace solution_61_points { void run(int n); };

void run(int n) { solution_100_points::run(n); }

////////////////////////////////////////////////////////////////////////////////
struct Dsu {
    int set_head[maxn];
    list<int> data[maxn];

    Dsu() {}
    Dsu(int n) {
        rep(i, n) {
            set_head[i] = i;
            data[i].assign(1, i);
        }
    }
    
    int find_set(int u) { return u == set_head[u] ? u : set_head[u] = find_set(set_head[u]); }
    void join(int u, int v) {
        u = find_set(u);
        v = find_set(v);
        if (u == v) return ;
        if (rand(2)) swap(u, v);
        set_head[u] = v;
        data[v].splice(data[v].end(), data[u]);  // this is O(1)
    }
     
    template<class container, class result_container = container>
    result_container get_all_members(const container& a) {
        result_container ans;
        for (auto i: a) {
            copy(data[i].begin(), data[i].end(), back_inserter(ans));
        }
        return ans;
    }
};

///////////////////////////////////////////////////////////////////////////////////////////

namespace solution_100_points {
    struct huffman_node {
        list<int> data;
        int depth;
        huffman_node *lchild, *rchild;

        huffman_node(const list<int>& data_) :data(data_), lchild(nullptr), rchild(nullptr) {}
        huffman_node(huffman_node* lchild_, huffman_node* rchild_)
            : lchild(lchild_), rchild(rchild_)
        {
            copy(lchild->data.begin(), lchild->data.end(), back_inserter(data));
            copy(rchild->data.begin(), rchild->data.end(), back_inserter(data));
        }

        ~huffman_node() {
            if (lchild) delete lchild;
            if (rchild) delete rchild;
        }

        void calculate_depth(int cur_depth = 0) {
            depth = cur_depth;
            if (lchild) lchild->calculate_depth(cur_depth + 1);
            if (rchild) rchild->calculate_depth(cur_depth + 1);
        }

        tuple<list<int>, list<int>> get_data(int level) {
            if (level < depth) { return {{}, {}}; }
            if (level == depth) {
                return { lchild ? lchild->data : list<int>(), rchild ? rchild->data : list<int>()};
            }

            list<int> left, right, child_left, child_right;
            if (lchild) {
                tie(left, right) = lchild->get_data(level);
            }
            if (rchild) {
                tie(child_left, child_right) = rchild->get_data(level);
                left.splice(left.end(), child_left);
                right.splice(right.end(), child_right);
            }
            return {left, right};
        }
    };

    tuple<list<int>, list<int>> split_in_half(const list<int>& u) {
        list<int> res[2];
        bool cur = 0;
        for (int i: u) {
            res[cur].push_back(i);
            cur = !cur;
        }
        return {res[0], res[1]};
    }

    huffman_node* build_huffman_tree(vector<list<int>> const& datas) {
        struct cmp {
            bool operator()(huffman_node* u, huffman_node* v) {
                if (len(u->data) == len(v->data)) return u < v;
                return len(u->data) < len(v->data);
            }
        };

        set<huffman_node*, cmp> pq;
        for (auto& i: datas) pq.insert(new huffman_node(i));

        while (len(pq) > 1) {
            auto u = *pq.begin(); pq.erase(pq.begin());
            auto v = *pq.begin(); pq.erase(pq.begin());
            pq.insert(new huffman_node(u, v));
        }
        return *pq.begin();
    }

    void run(int n) {
        Dsu dsu(n + 1);
        rep(edge, n - 1) {
            // query_cnt = 0;
            vector<list<int>> subsets;
            rep1(i, n)
                if (dsu.find_set(i) == i)
                    subsets.push_back(dsu.data[i]);
            auto huff_root = build_huffman_tree(subsets);
            huff_root->calculate_depth();
            list<int> left, right;

            int joined_level = 0;
            for (; ;++joined_level) {
                tie(left, right) = huff_root->get_data(joined_level);
                if (query(left, right) == 1) break;
            }


            huffman_node* joined_node = huff_root;
            while (joined_node->depth < joined_level) {
                assert(joined_node->lchild or joined_node->rchild);
                if (!joined_node->lchild) joined_node = joined_node->rchild;
                else if (!joined_node->rchild) joined_node = joined_node->lchild;
                else {
                    tie(left, right) = joined_node->lchild->get_data(joined_level);
                    if (query(left, right)) joined_node = joined_node->lchild;
                    else joined_node = joined_node->rchild;
                }
            }
            list<int> u, v;
            tie(u, v) = joined_node->get_data(joined_level);
            while (len(u) > 1) {
                tie(left, right) = split_in_half(u);
                if (query(left, v)) u = left;
                else u = right;
            }
            while (len(v) > 1) {
                tie(left, right) = split_in_half(v);
                if (query(left, u)) v = left;
                else v = right;
            }
            int a = *u.begin(), b = *v.begin();
            setRoad(a, b);
            dsu.join(a, b);
            // clog << query_cnt << endl;
            delete huff_root;
        }
    }
}

///////////////////////////////////////////////////////////////////////////////////////////

namespace solution_61_points {
    tuple<vector<int>, vector<int>> random_split(vector<int> a) {
        random_shuffle(a.begin(), a.end(), rand<int>);
        auto mid = a.begin() + len(a) / 2;
        return {vector<int>(a.begin(), mid), vector<int>(mid, a.end())};
    }
     
    void run(int n) {
        Dsu dsu(n + 1);
     
        int n_query = 0;
        rep(edge_num, n - 1) {
            vector<int> head;
            rep1(i, n) 
                if (dsu.find_set(i) == i) head.push_back(i);
     
            vector<int> u, v;
            do {
                tie(u, v) = random_split(head);
                u = dsu.get_all_members(u);
                v = dsu.get_all_members(v);
                ++n_query;
            } while (query(u, v) == 0);
     
            vector<int> left, right;
     
            while (len(u) > 1) {
                tie(left, right) = random_split(u);
                ++n_query;
                if (query(left, v) == 1) u = move(left);
                else u = move(right);
            }
     
            while (len(v) > 1) {
                tie(left, right) = random_split(v);
                ++n_query;
                if (query(u, left) == 1) v = move(left);
                else v = move(right);
            }
     
            int a = u[0], b = v[0];
            setRoad(a, b);
            dsu.join(a, b);
            // clog << edge_num << ' ' << a << ' ' << b <<  ' ' << n_query << endl;
        }
    }
};

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Ok! 99 queries used.
2 Correct 8 ms 504 KB Ok! 94 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 504 KB Ok! 498 queries used.
2 Correct 41 ms 504 KB Ok! 526 queries used.
3 Correct 42 ms 632 KB Ok! 523 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 620 KB Ok! 1271 queries used.
2 Correct 136 ms 632 KB Ok! 1270 queries used.
3 Correct 117 ms 504 KB Ok! 1191 queries used.
4 Correct 140 ms 624 KB Ok! 1289 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 504 KB Ok! 1244 queries used.
2 Correct 140 ms 632 KB Ok! 1246 queries used.
3 Correct 137 ms 504 KB Ok! 1264 queries used.
4 Correct 130 ms 632 KB Ok! 1246 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 660 KB Ok! 1256 queries used.
2 Correct 137 ms 620 KB Ok! 1256 queries used.
3 Correct 143 ms 632 KB Ok! 1254 queries used.
4 Correct 145 ms 628 KB Ok! 1294 queries used.
5 Correct 141 ms 620 KB Ok! 1272 queries used.
6 Correct 147 ms 664 KB Ok! 1283 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 632 KB Ok! 1275 queries used.
2 Correct 137 ms 632 KB Ok! 1269 queries used.