oj.uz

Submission #137840

# Submission time Handle Problem Language Result Execution time Memory
137840 2019-07-28T11:01:34 Z darkkcyan ICC (CEOI16_icc) C++14
61 / 100
 221 ms 632 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);
}

template<class container>
int query(const container& a, const container& b) {
    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);
}

#define maxn 111
int set_head[maxn];
list<int> data[maxn];
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>
vector<int> get_all_members(const container& a) {
    vector<int> ans;
    for (auto i: a) {
        copy(data[i].begin(), data[i].end(), back_inserter(ans));
    }
    return ans;
}

tuple<vector<int>, vector<int>> random_split(vector<int> a) {
    random_shuffle(a.begin(), a.end(), rand<int>);
    auto mid = a.begin() + (len(a) + rand(2)) / 2;
    return {vector<int>(a.begin(), mid), vector<int>(mid, a.end())};
}

void run(int n) {
    rep1(i, n) {
        set_head[i] = i;
        data[i].assign(1, i);
    }

    rep(edge_num, n - 1) {
        vector<int> head;
        rep1(i, n) 
            if (set_head[i] == i) head.push_back(i);

        vector<int> u, v;
        vector<int> left, right;

        vector<vector<int>> subsets;
        subsets.push_back(head);
        do {
            vector<vector<int>> new_subsets;
            u.clear(); v.clear();
            for (auto& i: subsets) {
                tie(left, right) = random_split(i);
                if (len(left)) new_subsets.push_back(left);
                if (len(right)) new_subsets.push_back(right);
                copy(left.begin(), left.end(), back_inserter(u));
                copy(right.begin(), right.end(), back_inserter(v));
            }
            u = get_all_members(u);
            v = get_all_members(v);
        } while (query(u, v) == 0);


        while (len(u) > 1) {
            tie(left, right) = random_split(u);
            if (query(left, v) == 1) u = move(left);
            else u = move(right);
        }

        while (len(v) > 1) {
            tie(left, right) = random_split(v);
            if (query(u, left) == 1) v = move(left);
            else v = move(right);
        }

        int a = u[0], b = v[0];
        setRoad(a, b);
        join(a, b);
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Ok! 101 queries used.
2 Correct 9 ms 504 KB Ok! 100 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 504 KB Ok! 534 queries used.
2 Correct 65 ms 632 KB Ok! 818 queries used.
3 Correct 60 ms 504 KB Ok! 768 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 572 KB Ok! 1504 queries used.
2 Correct 221 ms 568 KB Ok! 2104 queries used.
3 Correct 163 ms 588 KB Ok! 1624 queries used.
4 Correct 173 ms 504 KB Ok! 1681 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 508 KB Ok! 1617 queries used.
2 Correct 167 ms 564 KB Ok! 1646 queries used.
3 Correct 197 ms 552 KB Ok! 1902 queries used.
4 Correct 162 ms 504 KB Ok! 1601 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 200 ms 632 KB Too many queries! 1919 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 198 ms 632 KB Too many queries! 1911 out of 1625
2 Halted 0 ms 0 KB -