Submission #1272505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272505		Aviansh	ICC (CEOI16_icc)	C++20	100 / 100	81 ms	632 KiB

icc

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

struct dsu{
    vector<int>root;
    vector<int>siz;
    vector<set<int>>childs;
    dsu(int n){
        root=vector<int>(n);
        iota(root.begin(),root.end(),0);
        siz=vector<int>(n,1);
        childs=vector<set<int>>(n);
        for(int i = 0;i<n;i++)
            childs[i].insert(i);
    }

    bool unite(int x, int y){
        x=findRoot(x);
        y=findRoot(y);
        if(x==y)
            return 0;
        if(siz[x]<siz[y]){
            swap(x,y);
        }
        siz[x]+=siz[y];
        root[y]=x;
        for(int i : childs[y]){
            childs[x].insert(i);
        }
        return 1;
    }

    int findRoot(int x){
        if(x==root[x]){
            return x;
        }
        return root[x]=findRoot(root[x]);
    }
};

void run(int n){
    dsu ds(n);
    for(int i = 0;i<n-1;i++){
        set<int>s;
        for(int i = 0;i<n;i++){
            s.insert(ds.findRoot(i));
        }
        vector<int>arr;
        for(int i : s){
            arr.push_back(i);
        }
        vector<int>par1;
        vector<int>par2;
        int arr1[n];
        int arr2[n];
        int n1 = 0;
        int n2 = 0;
        int bit = 0;
        int good = 0;
        int x = 0;
        map<int,int>mp;
        for(int i = 0;i<arr.size();i++){
            mp[arr[i]]=i;
        }
        while(bit<ceil(log2(arr.size()))){
            par1.clear();
            par2.clear();
            while(par1.size()==0&&par2.size()==0){
                par1.clear();
                par2.clear();
                for(int i : arr){
                    if(mp[i]&(1<<bit))
                        par1.push_back(i);
                    else{
                        par2.push_back(i);
                    }
                }
                bit++;
            }
            n1 = 0;
            n2 = 0;
            for(int i = 0;i<par1.size();i++){
                for(int v : ds.childs[par1[i]]){
                    arr1[n1++]=v+1;
                }
            }
            for(int i = 0;i<par2.size();i++){
                for(int v : ds.childs[par2[i]]){
                    arr2[n2++]=v+1;
                }
            }
            if(n1&&n2&&query(n1,n2,arr1,arr2)){
                good+=(1<<(bit-1));
                x=bit-1;
            }
        }

        //now determine both components

        int A=0;
        int B=0;
        B+=(1<<x);
        for(int bit = 0;bit<ceil(log2(arr.size()));bit++){
            if(bit==x){
                continue;
            }
            par1.clear();
            par2.clear();
            if(good&(1<<bit)){
                //both different
                for(int i : arr){
                    if(mp[i]&(1<<x)){
                        if(mp[i]&(1<<bit))
                            par1.push_back(i);
                    }
                    else{
                        if(mp[i]&(1<<bit)){

                        }
                        else{
                            par2.push_back(i);
                        }
                    }
                }
                n1 = 0;
                n2 = 0;
                for(int i = 0;i<par1.size();i++){
                    for(int v : ds.childs[par1[i]]){
                        arr1[n1++]=v+1;
                    }
                }
                for(int i = 0;i<par2.size();i++){
                    for(int v : ds.childs[par2[i]]){
                        arr2[n2++]=v+1;
                    }
                }
                if(n1&&n2&&query(n1,n2,arr1,arr2)){
                    B+=(1<<bit);
                }
                else{
                    A+=(1<<bit);
                }
            }
            else{
                //both same
                for(int i : arr){
                    if(mp[i]&(1<<bit)){
                        continue;
                    }
                    if(mp[i]&(1<<x)){
                        par1.push_back(i);
                    }
                    else{
                        par2.push_back(i);
                    }
                }
                n1 = 0;
                n2 = 0;
                for(int i = 0;i<par1.size();i++){
                    for(int v : ds.childs[par1[i]]){
                        arr1[n1++]=v+1;
                    }
                }
                for(int i = 0;i<par2.size();i++){
                    for(int v : ds.childs[par2[i]]){
                        arr2[n2++]=v+1;
                    }
                }
                if(n1&&n2&&query(n1,n2,arr1,arr2)){
                    //this means both are 0
                }
                else{
                    A+=(1<<bit);
                    B+=(1<<bit);
                }
            }
        }

        //A and B discovered

        A=arr[A];
        B=arr[B];

        n1=0;
        for(int i : ds.childs[A]){
            arr1[n1++]=i+1;
        }
        n2=0;
        for(int i : ds.childs[B]){
            arr2[n2++]=i+1;
        }

        //now we bin search twice

        //bin search on 1
        int lo = 0;
        int hi = n1-1;
        while(lo<hi){
            int mid = (lo+hi)/2;
            int temparr[n];
            for(int i = 0;i<=mid;i++){
                temparr[i]=arr1[i];
            }
            if(n2&&query(mid+1,n2,temparr,arr2)){
                hi=mid;
            }
            else{
                lo=mid+1;
            }
        }
        int a = arr1[lo];
        lo=0;
        hi=n2-1;
        while(lo<hi){
            int mid = (lo+hi)/2;
            int temparr[n];
            for(int i = 0;i<=mid;i++){
                temparr[i]=arr2[i];
            }
            if(n1&&query(mid+1,n1,temparr,arr1)){
                hi=mid;
            }
            else{
                lo=mid+1;
            }
        }
        int b = arr2[lo];
        setRoad(a,b);
        ds.unite(a-1,b-1);
    }
}

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