oj.uz

Submission #960444

# Submission time Handle Problem Language Result Execution time Memory
960444 2024-04-10T13:14:49 Z Ghetto ICC (CEOI16_icc) C++17
100 / 100
 85 ms 856 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Ok! 94 queries used.
2 Correct 4 ms 604 KB Ok! 99 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 604 KB Ok! 540 queries used.
2 Correct 24 ms 604 KB Ok! 570 queries used.
3 Correct 24 ms 600 KB Ok! 580 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 600 KB Ok! 1425 queries used.
2 Correct 71 ms 632 KB Ok! 1390 queries used.
3 Correct 78 ms 604 KB Ok! 1593 queries used.
4 Correct 75 ms 624 KB Ok! 1479 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 604 KB Ok! 1491 queries used.
2 Correct 81 ms 632 KB Ok! 1502 queries used.
3 Correct 74 ms 628 KB Ok! 1486 queries used.
4 Correct 81 ms 600 KB Ok! 1475 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 856 KB Ok! 1503 queries used.
2 Correct 74 ms 628 KB Ok! 1468 queries used.
3 Correct 74 ms 600 KB Ok! 1500 queries used.
4 Correct 75 ms 636 KB Ok! 1513 queries used.
5 Correct 72 ms 640 KB Ok! 1485 queries used.
6 Correct 74 ms 604 KB Ok! 1507 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 604 KB Ok! 1519 queries used.
2 Correct 73 ms 600 KB Ok! 1415 queries used.