oj.uz

Submission #137836

# Submission time Handle Problem Language Result Execution time Memory
137836 2019-07-28T10:39:53 Z darkkcyan ICC (CEOI16_icc) C++14
61 / 100
 220 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) / 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);
    }

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

        vector<int> u, v;
        do {
            tie(u, v) = random_split(head);
            u = get_all_members(u);
            v = 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);
        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! 105 queries used.
2 Correct 9 ms 504 KB Ok! 106 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 632 KB Ok! 548 queries used.
2 Correct 66 ms 504 KB Ok! 851 queries used.
3 Correct 59 ms 560 KB Ok! 774 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 504 KB Ok! 1538 queries used.
2 Correct 220 ms 580 KB Ok! 2115 queries used.
3 Correct 159 ms 504 KB Ok! 1585 queries used.
4 Correct 175 ms 504 KB Ok! 1741 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 604 KB Ok! 1650 queries used.
2 Correct 162 ms 504 KB Ok! 1608 queries used.
3 Correct 183 ms 504 KB Ok! 1811 queries used.
4 Correct 155 ms 564 KB Ok! 1560 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 195 ms 608 KB Too many queries! 1898 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 195 ms 568 KB Too many queries! 1914 out of 1625
2 Halted 0 ms 0 KB -