제출 #1161667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161667		JordanTs	ICC (CEOI16_icc)	C++20	0 / 100	4 ms	584 KiB

icc

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

const int MAXN = 101;
int Root[MAXN];
int Size[MAXN];
set<int> Leaders;
vector<int> Vertexes[MAXN];

int Find(int U)
{
    if(Root[U] == U) return U;
    return Root[U] = Find(Root[U]);
}

void Merge(int U, int V)
{
    U = Find(U);
    V = Find(V);
    if(U == V) return;
    if(Size[U] > Size[V]) swap(U, V);
    Size[U] += Size[V];
    Root[V] = Root[U];
    for(auto& Vertex : Vertexes[V]) Vertexes[U].push_back(Vertex);
    Vertexes[V].clear();
    Leaders.erase(V);
}

void Conquer(vector<int> A, vector<int> B)
{
    if(A.empty() || B.empty()) return;
    int SizeA = (int)A.size();
    int SizeB = (int)B.size();
    int QueryA[MAXN] = {};
    int QueryB[MAXN] = {};

    for(int i = 0; i < SizeA; i++) QueryA[i] = A[i];
    for(int i = 0; i < SizeB; i++) QueryB[i] = B[i];

    if(SizeA == 1 && SizeB == 1)
    {
        setRoad(A[0], B[0]);
        Merge(A[0], B[0]);
        return;
    }

    if(SizeB > 1)
    {
        int SizeC = SizeB / 2;
        vector<int> C;

        for(int i = 0; i < SizeC; i++)
        {
            QueryB[i] = B[i];
            C.push_back(B[i]);
        }

        if(query(SizeA, SizeC, QueryA, QueryB) == 0)
        {
            C.clear();

            for(int i = SizeC; i < SizeB; i++)
            {
                C.push_back(B[i]);
            }
        }

        Conquer(A, C);
    }
    else
    {
        int SizeC = SizeA / 2;
        vector<int> C;
        for(int i = 0; i < SizeC; i++)
        {
            QueryA[i] = A[i];
            C.push_back(A[i]);
        }

        if(query(SizeC, SizeB, QueryA, QueryB) == 0)
        {
            C.clear();

            for(int i = SizeC; i < SizeA; i++)
            {
                C.push_back(A[i]);
            }
        }

        Conquer(C, B);
    }
}

void Divide(vector<int> A, vector<int> B, bool Lamp)
{
    if(A.empty() || B.empty()) return;
    int SizeA = 0;
    int SizeB = 0;
    int QueryA[MAXN] = {};
    int QueryB[MAXN] = {};

    for(int i = 0; i < (int)A.size(); i++)
    {
        for(auto& U : Vertexes[A[i]])
        {
            QueryA[SizeA] = U;
            SizeA++;
        }
    }

    for(int i = 0; i < (int)B.size(); i++)
    {
        for(auto& U : Vertexes[B[i]])
        {
            QueryB[SizeB] = U;
            SizeB++;
        }
    }

    if(Lamp || query(SizeA, SizeB, QueryA, QueryB) == 1)
    {
        if((int)A.size() == 1 && (int)B.size() == 1)
        {
            Conquer(Vertexes[A[0]], Vertexes[B[0]]);
            return;
        }

        if((int)B.size() > 1)
        {
            int SizeC = 0, QSizeC = (int)B.size() / 2;
            vector<int> C;

            for(int i = 0; i < QSizeC; i++)
            {
                C.push_back(B[i]);

                for(auto& U : Vertexes[B[i]])
                {
                    QueryB[SizeC] = U;
                    SizeC++;
                }
            }

            if(query(SizeA, SizeC, QueryA, QueryB) == 0)
            {
                C.clear();

                for(int i = QSizeC; i < (int)B.size(); i++)
                {
                    C.push_back(B[i]);
                }
            }

            Divide(A, C, true);
        }
        else
        {
            int SizeC = 0, QSizeC = (int)A.size() / 2;
            vector<int> C;

            for(int i = 0; i < QSizeC; i++)
            {
                C.push_back(A[i]);

                for(auto& U : Vertexes[A[i]])
                {
                    QueryA[SizeC] = U;
                    SizeC++;
                }
            }

            if(query(SizeC, SizeB, QueryA, QueryB) == 0)
            {
                C.clear();

                for(int i = QSizeC; i < (int)A.size(); i++)
                {
                    C.push_back(A[i]);
                }
            }

            Divide(C, B, true);
        }
    }
    else
    {
        int SizeC = 0, SizeD = 0;
        vector<int> C, D;

        for(int i = 0; i < (int)A.size(); i++)
        {
            if(i < (int)A.size() / 2)
            {
                C.push_back(A[i]);
                for(auto& U : Vertexes[A[i]])
                {
                    QueryA[SizeC] = U;
                    SizeC++;
                }
            }
            else
            {
                D.push_back(A[i]);
                for(auto& U : Vertexes[A[i]])
                {
                    QueryB[SizeD] = U;
                    SizeD++;
                }
            }
        }

        if(query(SizeC, SizeD, QueryA, QueryB) == 0)
        {
            C.clear();
            D.clear();
            int SizeC = (int)B.size() / 2;

            for(int i = 0; i < (int)B.size(); i++)
            {
                if(i < SizeC)
                {
                    C.push_back(B[i]);
                }
                else
                {
                    D.push_back(B[i]);
                }
            }
        }

        Divide(C, D, true);
    }

    return;
}

void run(int N)
{
    for(int U = 1; U <= N; U++)
    {
        Root[U] = U;
        Size[U] = 1;
        Vertexes[U].push_back(U);
        Leaders.insert(U);
    }

    int Edges = N - 1;

    while(Edges--)
    {
        int SizeA = (int)Leaders.size() / 2;
        int Index = 0;
        vector<int> A, B;

        for(auto& U : Leaders)
        {
            if(Index < SizeA)
            {
                A.push_back(U);
            }
            else
            {
                B.push_back(U);
            }

            Index++;
        }

        Divide(A, B, false);
    }
}

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