Submission #341601

#	Time	Username	Problem	Language	Result	Execution time	Memory
341601		phathnv	ICC (CEOI16_icc)	C++11	100 / 100	150 ms	620 KiB

icc

#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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10