Submission #960444

#	Time	Username	Problem	Language	Result	Execution time	Memory
960444		Ghetto	ICC (CEOI16_icc)	C++17	100 / 100	85 ms	856 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 100 + 5;

int n;

int par[MAX_N];
vector<int> mems[MAX_N];
void init() {
    for (int i = 1; i <= n; i++) {
        par[i] = i;
        mems[i].push_back(i);
    }
}
int find_par(int u) {
    if (par[u] == u) return u;
    par[u] = find_par(par[u]);
    return par[u];
}
void merge(int u, int v) {
    u = find_par(u);
    v = find_par(v);
    assert(u != v);
    
    if (mems[u].size() < mems[v].size()) swap(u, v);
    par[v] = u;
    for (int mem : mems[v]) mems[u].push_back(mem);
}

bool safe_query(vector<int> els1, vector<int> els2) {
    int size1 = els1.size(), size2 = els2.size();
    int el1[size1], el2[size2];
    for (int i = 0; i < size1; i++) el1[i] = els1[i];
    for (int i = 0; i < size2; i++) el2[i] = els2[i];
    return query(size1, size2, el1, el2);
}

int bin_search(vector<int> els1, vector<int> els2) { // Returns el not ind
    int lo = 0, hi = els1.size() - 1;
    while (lo != hi) {
        int mid = (lo + hi) / 2;
        vector<int> tmp_els1;
        for (int i = lo; i <= mid; i++) tmp_els1.push_back(els1[i]);
        bool resp = safe_query(tmp_els1, els2);

        if (resp) hi = mid;
        else lo = mid + 1;
    }
    return els1[lo];
}

void do_time() {
    vector<int> nodes;
    for (int i = 1; i <= n; i++)
        if (find_par(i) == i) nodes.push_back(i);
    int n_nodes = nodes.size();
    assert(n_nodes >= 2);

    vector<pii> ones = {{0, (n_nodes - 1) / 2}};
    vector<pii> twos = {{(n_nodes - 1) / 2 + 1, n_nodes - 1}};
    while (true) {
        vector<int> tmp_ones, tmp_twos;
        for (pii range : ones)
            for (int i = range.first; i <= range.second; i++)
                for (int u : mems[nodes[i]])
                    tmp_ones.push_back(u);
        for (pii range : twos)
            for (int i = range.first; i <= range.second; i++)
                for (int u : mems[nodes[i]])
                    tmp_twos.push_back(u);
        bool resp = safe_query(tmp_ones, tmp_twos);

        if (resp) break;
        vector<pii> new_ones, new_twos;
        for (pii range : ones) {
            int lo = range.first, hi = range.second;
            if (lo == hi) continue;
            int mid = (lo + hi) / 2;
            new_ones.push_back({lo, mid});
            new_twos.push_back({mid + 1, hi});
        }
        for (pii range : twos) {
            int lo = range.first, hi = range.second;
            if (lo == hi) continue;
            int mid = (lo + hi) / 2;
            new_ones.push_back({lo, mid});
            new_twos.push_back({mid + 1, hi});
        }
        ones.swap(new_ones);
        twos.swap(new_twos);
    }

    vector<int> one_nodes, two_nodes;
    for (pii range : ones)
        for (int i = range.first; i <= range.second; i++)
            for (int u : mems[nodes[i]])
                one_nodes.push_back(u);
    for (pii range : twos)
        for (int i = range.first; i <= range.second; i++)
            for (int u : mems[nodes[i]])
                two_nodes.push_back(u);
    // assert(safe_query(one_nodes, two_nodes));
    int one_ans = bin_search(one_nodes, two_nodes);
    // assert(safe_query({one_ans}, two_nodes));
    int two_ans = bin_search(two_nodes, one_nodes);
    // assert(safe_query({one_ans}, {two_ans}));
    setRoad(one_ans, two_ans);
    merge(one_ans, two_ans);    
}

void run(int tmp_n) {
    n = tmp_n;

    init();

    for (int i = 1; i <= n - 1; i++) do_time();
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10