oj.uz

Submission #566113

# Submission time Handle Problem Language Result Execution time Memory
566113 2022-05-21T20:09:27 Z piOOE ICC (CEOI16_icc) C++17
90 / 100
 144 ms 516 KB 
#include "icc.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)
#define sz(x) ((int)size(x))
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

int ask(vector<int> a, vector<int> b) {
    for (int &x : a) ++x;
    for (int &y : b) ++y;
    return query(sz(a), sz(b), a.data(), b.data());
}

vector<int> p;

int get(int a) {
    return a == p[a] ? a : p[a] = get(p[a]);
}

bool mrg(int a, int b) {
    a = get(a), b = get(b);
    if (a == b) {
        return false;
    }
    p[b] = a;
    return true;
}

void run(int n) {
    p.resize(n);
    iota(all(p), 0);
    for (int cnt = 1; cnt < n; ++cnt) {
        vector<int> v;
        for (int i = 0; i < n; ++i) {
            if (p[i] == i) v.push_back(i);
        }
        assert(sz(p) > 1);
        vector<vector<int>> f, s;
        f.emplace_back(), s.emplace_back();
        for (int i = 0; i < sz(v); ++i) {
            if (i & 1) s.back().push_back(v[i]);
            else f.back().push_back(v[i]);
        }
        while (true) {
            vector<int> a, b;
            for (auto &x: f) {
                for (int y: x) {
                    for (int i = 0; i < n; ++i) {
                        if (get(i) == y) a.push_back(i);
                    }
                }
            }
            for (auto &x: s) {
                for (int y: x) {
                    for (int i = 0; i < n; ++i) {
                        if (get(i) == y) b.push_back(i);
                    }
                }
            }
            if (ask(a, b)) break;
            vector<vector<int>> ff, ss;
            for (auto &x: f) {
                ff.emplace_back();
                ss.emplace_back();
                for (int i = 0; i < sz(x); ++i) {
                    if (i & 1) ss.back().push_back(x[i]);
                    else ff.back().push_back(x[i]);
                }
                if (ss.back().empty()) ss.pop_back();
                if (ff.back().empty()) ff.pop_back();
            }
            for (auto &x: s) {
                ff.emplace_back();
                ss.emplace_back();
                for (int i = 0; i < sz(x); ++i) {
                    if (i & 1) ss.back().push_back(x[i]);
                    else ff.back().push_back(x[i]);
                }
                if (ss.back().empty()) ss.pop_back();
                if (ff.back().empty()) ff.pop_back();
            }
            swap(f, ff);
            swap(s, ss);
        }
        {
            vector<int> a, b;
            for (auto &x: f) {
                for (int y: x) {
                    for (int i = 0; i < n; ++i) {
                        if (get(i) == y) a.push_back(i);
                    }
                }
            }
            for (auto &x: s) {
                for (int y: x) {
                    for (int i = 0; i < n; ++i) {
                        if (get(i) == y) b.push_back(i);
                    }
                }
            }
            int l = 0, r = sz(b);
            while (l + 1 < r) {
                int m = (l + r) >> 1;
                vector<int> c;
                for (int i = l; i < m; ++i) {
                    c.push_back(b[i]);
                }
                if (ask(a, c)) r = m;
                else l = m;
            }
            int v1 = b[l];
            l = 0, r = sz(a);
            while (l + 1 < r) {
                int m = (l + r) >> 1;
                vector<int> c;
                for (int i = l; i < m; ++i) {
                    c.push_back(a[i]);
                }
                if (ask({v1}, c)) r = m;
                else l = m;
            }
            int v2 = a[l];
            setRoad(v1 + 1, v2 + 1);
            mrg(v1, v2);
        }
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Ok! 94 queries used.
2 Correct 5 ms 468 KB Ok! 105 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 468 KB Ok! 548 queries used.
2 Correct 40 ms 468 KB Ok! 692 queries used.
3 Correct 37 ms 488 KB Ok! 702 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 484 KB Ok! 1425 queries used.
2 Correct 142 ms 468 KB Ok! 1704 queries used.
3 Correct 144 ms 500 KB Ok! 1579 queries used.
4 Correct 129 ms 512 KB Ok! 1525 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 496 KB Ok! 1490 queries used.
2 Correct 132 ms 492 KB Ok! 1525 queries used.
3 Correct 131 ms 504 KB Ok! 1704 queries used.
4 Correct 114 ms 492 KB Ok! 1497 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 492 KB Ok! 1705 queries used.
2 Correct 142 ms 500 KB Ok! 1671 queries used.
3 Correct 125 ms 500 KB Ok! 1673 queries used.
4 Correct 137 ms 516 KB Ok! 1664 queries used.
5 Correct 118 ms 488 KB Ok! 1490 queries used.
6 Correct 125 ms 508 KB Ok! 1551 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 516 KB Too many queries! 1671 out of 1625
2 Halted 0 ms 0 KB -