Submission #1271857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271857		VMaksimoski008	ICC (CEOI16_icc)	C++20	100 / 100	87 ms	620 KiB

icc

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

struct union_find {
    int n;
    vector<int> par, size;
    vector<vector<int> > st;

    union_find(int _n) : n(_n), par(n+1), size(n+1, 1), st(n+1) {
        for(int i=1; i<=n; i++) {
            par[i] = i;
            st[i].push_back(i);
        }
    }

    int find(int u) {
        if(u == par[u]) return u;
        return par[u] = find(par[u]);
    }

    void uni(int a, int b) {
        a = find(a); b = find(b);
        if(a == b) return ;
        if(size[a] < size[b]) swap(a, b);
        for(int &u : st[b]) st[a].push_back(u);
        size[a] += size[b];
        par[b] = a;
    }

    bool same_set(int a, int b) {
        return find(a) == find(b);
    }
} dsu(105);

int __query(vector<int> &x, vector<int> &y) {
    int kur[x.size()], picka[y.size()];
    for(int i=0; i<x.size(); i++)
        kur[i] = x[i];
    for(int i=0; i<y.size(); i++)
        picka[i] = y[i];
    return query(x.size(), y.size(), kur, picka);
}

int _query(vector<int> &a, vector<int> &b) {
    vector<int> x, y;
    for(int u : a)
        for(int v : dsu.st[u])
            x.push_back(v);
    for(int u : b)
        for(int v : dsu.st[u])
            y.push_back(v);
    return __query(x, y);
}

void run(int n) {
    //ICC = Egoi25 Dark Ride

    for(int _=1; _<n; _++) {
        vector<int> babi;
        for(int i=1; i<=n; i++)
            if(dsu.find(i) == i) babi.push_back(i);

        int XOR = 0, bit = -1;
        for(int b=0; (1<<b)<=n; b++) {
            vector<int> v1, v2;
            for(int u : babi) {
                if(u & (1 << b)) v1.push_back(u);
                else v2.push_back(u);
            }

            if(_query(v1, v2)) {
                XOR ^= (1 << b);
                bit = b;
            }
        }

        vector<int> v1, v2;
        for(int u : babi) {
            if(u & (1 << bit)) {
                v1.push_back(u);
            } else {
                v2.push_back(u);
            }
        }

        int l=0, r=v1.size()-1, p=0;
        while(l <= r) {
            int m = (l + r) / 2;
            vector<int> v3;
            for(int i=0; i<=m; i++)
                v3.push_back(v1[i]);

            if(_query(v3, v2)) p = m, r = m - 1;
            else l = m + 1;
        }

        int pu = v1[p];
        int pv = pu ^ XOR;

        int u = 0;
        l=0, r=dsu.st[pu].size()-1;
        while(l <= r) {
            int m = (l + r) / 2;
            vector<int> v3;
            for(int i=0; i<=m; i++)
                v3.push_back(dsu.st[pu][i]);
            
            if(__query(v3, dsu.st[pv]))
                u = dsu.st[pu][m], r = m - 1;
            else
                l = m + 1;
        }

        int v = 0;
        l=0, r=dsu.st[pv].size()-1;
        while(l <= r) {
            int m = (l + r) / 2;
            vector<int> v3;
            for(int i=0; i<=m; i++)
                v3.push_back(dsu.st[pv][i]);

            if(__query(v3, dsu.st[pu]))
                v = dsu.st[pv][m], r = m - 1;
            else
                l = m + 1;
        }
        setRoad(u, v);
        dsu.uni(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