oj.uz

Submission #341601

# Submission time Handle Problem Language Result Execution time Memory
341601 2020-12-30T07:33:52 Z phathnv ICC (CEOI16_icc) C++11
100 / 100
 150 ms 620 KB 
#include <bits/stdc++.h>
#include "icc.h"

using namespace std;

typedef long long ll;

const int N = 101;

int n, root[N];

bool myQuery(vector <int> &a, vector <int> &b){
    if (a.empty() || b.empty())
        return 0;
    int res = query(a.size(), b.size(), a.data(), b.data());
    return res;
}

void mySetRoad(int u, int v){
    setRoad(u, v);
    u = root[u];
    v = root[v];
    if (u > v)
        swap(u, v);
    for(int i = 1; i <= n; i++)
        if (root[i] == v)
            root[i] = u;
}

pair <int, int> findEdge(){
    vector <int> a, b;
    bool flag = 0;
    for(int i = 0; i <= 6; i++){
        a.clear();
        b.clear();
        for(int u = 1; u <= n; u++)
            if (root[u] & (1 << i))
                a.push_back(u);
            else
                b.push_back(u);
        if (myQuery(a, b)){
            flag = 1;
            break;
        }
    }
    assert(flag);

    for(int t = 0; t < 2; t++){
        int l = 0, r = a.size() - 1;
        while (l < r){
            int mid = (l + r) >> 1;
            vector <int> tmp;
            for(int i = l; i <= mid; i++)
                tmp.push_back(a[i]);
            if (myQuery(tmp, b))
                r = mid;
            else
                l = mid + 1;
        }

        a = {a[l]};
        swap(a, b);
    }

    if (a[0] > b[0])
        swap(a, b);
    return {a[0], b[0]};
}

void run(int _n){
    n = _n;
    for(int i = 1; i <= n; i++)
        root[i] = i;
    for(int i = 1; i < n; i++){
        pair <int, int> edge = findEdge();
        mySetRoad(edge.first, edge.second);
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 492 KB Ok! 98 queries used.
2 Correct 7 ms 492 KB Ok! 100 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 492 KB Ok! 529 queries used.
2 Correct 47 ms 492 KB Ok! 653 queries used.
3 Correct 44 ms 492 KB Ok! 643 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 620 KB Ok! 1369 queries used.
2 Correct 144 ms 620 KB Ok! 1594 queries used.
3 Correct 113 ms 620 KB Ok! 1319 queries used.
4 Correct 128 ms 492 KB Ok! 1472 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 492 KB Ok! 1377 queries used.
2 Correct 125 ms 492 KB Ok! 1446 queries used.
3 Correct 142 ms 492 KB Ok! 1579 queries used.
4 Correct 111 ms 492 KB Ok! 1290 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 492 KB Ok! 1586 queries used.
2 Correct 138 ms 620 KB Ok! 1585 queries used.
3 Correct 143 ms 492 KB Ok! 1612 queries used.
4 Correct 133 ms 620 KB Ok! 1529 queries used.
5 Correct 122 ms 492 KB Ok! 1412 queries used.
6 Correct 134 ms 492 KB Ok! 1531 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 492 KB Ok! 1606 queries used.
2 Correct 150 ms 620 KB Ok! 1616 queries used.