Submission #101237

#	Time	Username	Problem	Language	Result	Execution time	Memory
101237		ShaneOng	ICC (CEOI16_icc)	C++14	18 / 100	437 ms	724 KiB

icc

#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
int n;
typedef pair<int,int> ii;
vector<int> p,rnk,adj[109];
int findS(int a){
    return a==p[a]?a:(p[a]=findS(p[a]));
}
void unionS(int a,int b){
    if(findS(a)!=findS(b)){
        int i=findS(a),j=findS(b);
        if(rnk[i]<rnk[j])
            p[i]=j;
        else{
            p[j]=i;
            if(rnk[i]==rnk[j])
                rnk[i]++;
        }
    }
}
vector<int> conv(vector<int> a){
    vector<int> newa;
    unordered_set<int> us;
    for(int x:a){
        us.insert(x);
    }
    for(int x=0;x<n;x++)
        if(us.find(findS(x))!=us.end())
            newa.push_back(x+1);
    return newa;
}
ii stuff(vector<int> a,vector<int> b){
    int qu=0;
    if((int)a.size()>0&&(int)b.size()>0){
        vector<int> tempa=conv(a),tempb=conv(b);
        qu=query(tempa.size(),tempb.size(),&tempa[0],&tempb[0]);
    }
    /*printf("\na:");
    for(int x:a)
        printf("%d ",x);
    printf("\n");
    printf("b:");
    for(int x:b)
        printf("%d ",x);
    printf("\n");*/
    int na=(int)a.size(),nb=(int)b.size();
    ii res=ii(-1,-1);
    if(qu==0){
        vector<int> aa,ab,ba,bb;
        if(na>1){
            for(int x=0;x<na;x++){
                if(x<na/2)
                    aa.push_back(a[x]);
                else
                    ab.push_back(a[x]);
            }
            res=max(res,stuff(aa,ab));
        }
        if(nb>1){
            for(int x=0;x<nb;x++){
                if(x<nb/2)
                    ba.push_back(b[x]);
                else
                    bb.push_back(b[x]);
            }
            res=max(res,stuff(ba,bb));
        }

        return res;
    }else{
        a=conv(a),b=conv(b);
        while((int)a.size()>1){
            vector<int> a1,a2;
            for(int x=0;x<(int)a.size();x++){
                if(x<(int)a.size()/2)
                    a1.push_back(a[x]);
                else
                    a2.push_back(a[x]);
            }

            int qu=query(a1.size(),b.size(),&a1[0],&b[0]);
            if(qu==0){
                a=a2;
            }else
                a=a1;
        }
        while((int)b.size()>1){
            vector<int> b1,b2;
            for(int x=0;x<(int)b.size();x++){
                if(x<(int)b.size()/2)
                    b1.push_back(b[x]);
                else
                    b2.push_back(b[x]);
            }
            int qu=query(a.size(),b1.size(),&a[0],&b1[0]);
            if(qu==0){
                b=b2;
            }else
                b=b1;
        }
        //printf("%d %d\n",a[0],b[0]);
        return ii(a[0],b[0]);

    }
}
void run(int nn) {
    n=nn;
    for(int x=0;x<n;x++){
        p.push_back(x);
        rnk.push_back(0);
    }
    for(int x=0;x<n-1;x++){
        int ctr=0;
        vector<int> arr[2];
        for(int y=0;y<n;y++){
            if(findS(y)==y){
                arr[ctr].push_back(y);
                ctr=1-ctr;
            }
        }
        ii ans=stuff(arr[0],arr[1]);
        adj[ans.first-1].push_back(ans.second-1);
        adj[ans.second-1].push_back(ans.first-1);
        unionS(ans.second-1,ans.first-1);
        //printf("%d %d\n",ans.first,ans.second);
        setRoad(ans.first,ans.second);
    }
}

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