Submission #1076812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076812		vjudge1	ICC (CEOI16_icc)	C++17	100 / 100	98 ms	632 KiB

icc

#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

#define isz(a) (int)(a).size()

const int NM = 100;

int parent[NM+5], sz[NM+5], id[NM+5], k;
vector <int> arr[NM+5];
vector <int> f, g;
int _X[NM+5], _Y[NM+5];

void make_set(int v){
    parent[v] = v;
    sz[v] = 1;
    arr[v] = {v};
}

int find_set(int v){
    return parent[v] == v ? v : parent[v] = find_set(parent[v]);
}

void union_sets(int u, int v){
    u = find_set(u);
    v = find_set(v);
    if (u == v) return;
    if (sz[u] < sz[v]) swap(u, v);
    parent[v] = u;
    sz[u] += sz[v];
    for (int x : arr[v]) arr[u].push_back(x);
    arr[v].clear();
}

int ask(vector <int> &X, vector <int> &Y){
	for (int i = 0; i < isz(X); i++) _X[i] = X[i];
	for (int i = 0; i < isz(Y); i++) _Y[i] = Y[i];
	return query(isz(X), isz(Y), _X, _Y);
}

void guess(int u, int v){
	setRoad(u, v);
}

void run(int n){
    for (int i = 1; i <= n; i++) make_set(i);
    for (int i = 1; i < n; i++){
        k = 0;
        for (int j = 1; j <= n; j++)
            if (parent[j] == j) id[k++] = j;
        
        int s = 0;
        for (int b = 0; b <= __lg(k-1); b++){
            vector <int> X = {}, Y = {};
            for (int j = 0; j < k; j++)
                for (int v : arr[id[j]])
                    if ((j>>b)&1) X.push_back(v); else Y.push_back(v);
            if (ask(X, Y)) s ^= (1<<b);
        }
        f.clear();
        g.clear();
        for (int u = 0; u < k; u++){
            int v = u^s;
            if (u < v && v < k){
                f.push_back(u);
                g.push_back(v);
            }
        }
        int l = 0, r = isz(f)-2, res = isz(f)-1;
        while (l <= r){
            int mid = (l+r)/2;
            vector <int> X = {}, Y = {};
            for (int j = 0; j <= mid; j++){
                for (int v : arr[id[f[j]]]) X.push_back(v);
                for (int v : arr[id[g[j]]]) Y.push_back(v);
            }
            if (ask(X, Y)){
                res = mid;
                r = mid-1;
            }
            else l = mid+1;
        }
        int resf = isz(arr[id[f[res]]])-1, resg = isz(arr[id[g[res]]])-1;
        l = 0, r = resf-1;
        while (l <= r){
            int mid = (l+r)/2;
            vector <int> X = {}, Y = arr[id[g[res]]];
            for (int j = 0; j <= mid; j++)
                X.push_back(arr[id[f[res]]][j]);
            if (ask(X, Y)){
                resf = mid;
                r = mid-1;
            }
            else l = mid+1;
        }
        l = 0, r = resg-1;
        while (l <= r){
            int mid = (l+r)/2;
            vector <int> X = arr[id[f[res]]], Y = {};
            for (int j = 0; j <= mid; j++)
                Y.push_back(arr[id[g[res]]][j]);
            if (ask(X, Y)){
                resg = mid;
                r = mid-1;
            }
            else l = mid+1;
        }
        int u = arr[id[f[res]]][resf], v = arr[id[g[res]]][resg];
        guess(u, v);
        union_sets(u, v);
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10