Submission #1143986

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

icc

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

int parent[105];
set<int> st[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(st[a].size() < st[b].size())
        swap(a, b);
    
    for(int x : st[b])
        st[a].insert(x);
    parent[b] = a;
}

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

    for(int z = 0; z < n-1; z++)
    {
        for(int i = 1; i <= n; i++)
        {
            int root = find(i);
            int arr[1] = {i};

            int bsize = n-st[root].size();
            int brr[bsize];
            int pos = 0;
            for(int j = 1; j <= n; j++)
            {
                if(i == j)
                    continue;
                if(st[root].count(j))
                    continue;
                brr[pos++] = j;
            }

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

                while(1)
                {   
                    if(bsize == 1)
                    {
                        setRoad(i, v[0]);
                        comb(i, v[0]);
                        break;
                    }

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

                break;
            }
        }
    }
}

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