Submission #1272489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272489		Aviansh	ICC (CEOI16_icc)	C++20	61 / 100	114 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);
    mt19937 rng(time(0));
    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);
        }
        int x = arr.size();
        vector<int>par1;
        vector<int>par2;
        int arr1[n];
        int arr2[n];
        int n1 = 0;
        int n2 = 0;
        while(1){
            par1.clear();
            par2.clear();
            for(int i : arr){
                par1.push_back(i);
            }
            for(int i = 0;i<x/2;i++){
                int ind = rng()%par1.size();
                swap(par1[ind],par1[par1.size()-1]);
                par2.push_back(par1.back());
                par1.pop_back();
            }
            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(query(n1,n2,arr1,arr2)){
                break;
            }
        }

        //now we bin search twice

        //bin search on 1
        int lo = 0;
        int hi = n1;
        while(lo<hi){
            int mid = (lo+hi)/2;
            int temparr[n];
            for(int i = 0;i<=mid;i++){
                temparr[i]=arr1[i];
            }
            if(query(mid+1,n2,temparr,arr2)){
                hi=mid;
            }
            else{
                lo=mid+1;
            }
        }
        int a = arr1[lo];
        lo=0;
        hi=n2;
        while(lo<hi){
            int mid = (lo+hi)/2;
            int temparr[n];
            for(int i = 0;i<=mid;i++){
                temparr[i]=arr2[i];
            }
            if(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: 0 / 29
• Subtask 6: 0 / 10