Submission #1244524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244524		urosk	ICC (CEOI16_icc)	C++20	100 / 100	76 ms	628 KiB

icc

#include "bits/stdc++.h"
#include "icc.h"
#define pb push_back
#define si(a_) (ll)(a_.size())

using namespace std;

using ll = int;

const ll maxn = 105;
const ll lg = 7;
ll n;
ll a[maxn];
ll b[maxn];
ll c[maxn];
ll asz = 0,bsz = 0,csz = 0;
ll dsu[maxn];
vector<ll> v[maxn];
set<ll> s;
ll root(ll x){
    while(x!=dsu[x]){
        x = dsu[x];
    }
    return x;
}
void upd(ll x,ll y){
    x = root(x), y = root(y);
    dsu[y] = x;
    for(ll u : v[y]) v[x].pb(u);
}
void run(ll N){
    n = N;
    for(ll i = 1;i<=n;i++){
        v[i].pb(i);
        dsu[i] = i;
    }
    // freopen("out.txt","w",stdout);
    for(ll ff = 0;ff<n-1;ff++){
        vector<ll> rut;
        s.clear();
        for(ll i = 1;i<=n;i++) s.insert(root(i));
        for(ll x : s) rut.pb(x);
        // cout<<"RUT: "<<endl;
        // for(ll x : s) cout<<x<< " "; cout<<endl;
        for(ll j = 0;j<lg;j++){
            asz = 0,bsz = 0;
            for(ll i = 0;i<si(rut);i++){
                if((1<<j)&i){
                    for(ll x : v[rut[i]]) a[asz++] = x;
                }else{
                    for(ll x : v[rut[i]]) b[bsz++] = x;
                }
            }
            // for(ll k = 0;k<asz;k++) cout<<a[k]<< " ";cout<<endl;
            // for(ll k = 0;k<bsz;k++) cout<<b[k]<< " ";cout<<endl;
            if(query(asz,bsz,a,b)){
                ll tl = 0,tr = bsz-1,mid;
                while(tl<tr){
                    mid = (tl+tr)/2;
                    csz = 0;
                    for(ll i = tl;i<=mid;i++) c[csz++] = b[i];
                    if(query(asz,csz,a,c)) tr = mid;
                    else tl = mid+1;
                }
                b[0] = b[tl];
                bsz = 1;
                tl = 0,tr = asz-1,mid;
                while(tl<tr){
                    mid = (tl+tr)/2;
                    csz = 0;
                    for(ll i = tl;i<=mid;i++) c[csz++] = a[i];
                    if(query(csz,bsz,c,b)) tr = mid;
                    else tl = mid+1;
                }
                setRoad(b[0],a[tl]);
                upd(b[0],a[tl]);
                // cout<<"rod: "<<b[0]<< " "<<a[tl]<<endl;
                break;
            }
        }
    }
}

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