oj.uz

답안 #566119

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
566119 2022-05-21T20:20:05 Z piOOE CEOI16_icc (CEOI16_icc) C++17
100 / 100
 108 ms 652 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]);
        }
        map<int, vector<int>> lst;
        for (auto a: f.back())
            lst[a] = s.back();
        for (auto a: s.back())
            lst[a] = f.back();
        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;
            lst.clear();
            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();
                    continue;
                }
                if (ff.back().empty()) {
                    ff.pop_back();
                    continue;
                }
                for (auto aa: ff.back())
                    lst[aa] = ss.back();
                for (auto aa: ss.back())
                    lst[aa] = ff.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();
                    continue;
                }
                if (ff.back().empty()) {
                    ff.pop_back();
                    continue;
                }
                for (auto aa: ff.back())
                    lst[aa] = ss.back();
                for (auto aa: ss.back())
                    lst[aa] = ff.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];
            {
                auto xx = lst[get(v1)];
                a.clear();
                for (int y: xx) {
                    for (int i = 0; i < n; ++i) {
                        if (get(i) == y) a.push_back(i);
                    }
                }
            }
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 468 KB Ok! 94 queries used.
2 Correct 4 ms 468 KB Ok! 96 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 504 KB Ok! 512 queries used.
2 Correct 30 ms 520 KB Ok! 499 queries used.
3 Correct 28 ms 520 KB Ok! 514 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 540 KB Ok! 1275 queries used.
2 Correct 105 ms 524 KB Ok! 1230 queries used.
3 Correct 103 ms 540 KB Ok! 1176 queries used.
4 Correct 103 ms 560 KB Ok! 1264 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 588 KB Ok! 1232 queries used.
2 Correct 102 ms 468 KB Ok! 1239 queries used.
3 Correct 106 ms 648 KB Ok! 1230 queries used.
4 Correct 99 ms 532 KB Ok! 1254 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 544 KB Ok! 1249 queries used.
2 Correct 103 ms 652 KB Ok! 1227 queries used.
3 Correct 106 ms 524 KB Ok! 1231 queries used.
4 Correct 106 ms 532 KB Ok! 1243 queries used.
5 Correct 99 ms 548 KB Ok! 1265 queries used.
6 Correct 106 ms 536 KB Ok! 1241 queries used.

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 540 KB Ok! 1227 queries used.
2 Correct 102 ms 536 KB Ok! 1230 queries used.