Submission #1144024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144024		MongHwa	ICC (CEOI16_icc)	C++20	18 / 100	183 ms	624 KiB

icc

#include "icc.h"
#include <vector>
#include <set>
using namespace std;

int parent[105];
bool skip[105];
set<int> comp[105];

int find(int x)
{
    if(parent[x] < 0)
        return x;
    parent[x] = find(parent[x]);
    return parent[x];
}

void comb(int a, int b)
{
    a = find(a);
    b = find(b);

    if(a == b)
        return;
    if(comp[a].size() < comp[b].size())
        swap(a, b);
    
    for(int x : comp[b])
        comp[a].insert(x);
    parent[b] = a;
    comp[b].clear();
}

void run(int n) {
    for(int i = 1; i <= n; i++)
    {
        parent[i] = -1;
        comp[i].insert(i);
    }

    for(int z = 0; z < n-1; z++)
    {
        fill(skip, skip+n+1, 0);
        for(int i = 1; i <= n; i++)
        {
            if(comp[i].empty())
                continue;
            
            int asize = comp[i].size();
            int arr[asize];
            int pos = 0;
            for(int x : comp[i])
                arr[pos++] = x;

            pos = 0;
            int bsize = n-asize;
            for(int j = 1; j <= n; j++)
                if(skip[j])
                    bsize--;
            
            int brr[bsize];
            for(int j = 1; j <= n; j++)
                if(!comp[i].count(j) && !skip[j])
                    brr[pos++] = j;

            if(query(asize, bsize, arr, brr))
            {
                int a, b;
                vector<int> v;
                for(int j = 0; j < asize; j++)
                    v.push_back(arr[j]);

                while(1)
                {   
                    if(asize == 1)
                    {
                        a = v[0];
                        break;
                    }

                    int trr[asize/2];
                    for(int j = 0; j < asize/2; j++)
                        trr[j] = v[j];
                    
                    if(query(asize/2, bsize, trr, brr))
                    {
                        v.erase(v.begin()+asize/2+1, v.end());
                        asize /= 2;
                        if(asize == 1)
                        {
                            a = v[0];
                            break;
                        }
                    }
                    else
                    {
                        v.erase(v.begin(), v.begin()+asize/2);
                        asize = asize/2 + asize%2;
                        if(asize == 1)
                        {
                            a = v[0];
                            break;
                        }
                    }
                }

                v.clear();
                for(int j = 0; j < bsize; j++)
                    v.push_back(brr[j]);

                int arr2[1] = {a};
                while(1)
                {   
                    if(bsize == 1)
                    {
                        b = v[0];
                        break;
                    }

                    int trr[bsize/2];
                    for(int j = 0; j < bsize/2; j++)
                        trr[j] = v[j];
                    
                    if(query(1, bsize/2, arr2, trr))
                    {
                        v.erase(v.begin()+bsize/2+1, v.end());
                        bsize /= 2;
                        if(bsize == 1)
                        {
                            b = v[0];
                            break;
                        }
                    }
                    else
                    {
                        v.erase(v.begin(), v.begin()+bsize/2);
                        bsize = bsize/2 + bsize%2;
                        if(bsize == 1)
                        {
                            b = v[0];
                            break;
                        }
                    }
                }

                setRoad(a, b);
                comb(a, b);
                break;
            }
            else
                for(int x : comp[i])
                    skip[x] = 1;
        }
    }
}

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