제출 #58051

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58051		MatheusLealV	ICC (CEOI16_icc)	C++17	0 / 100	4 ms	776 KiB

icc

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

set<int> grafo[N];

int pai[N], peso[N];

int Find(int x)
{
if(x == pai[x]) return x;

return pai[x] = Find(pai[x]);
}

void join(int a, int b)
{
a = Find(a), b = Find(b);

if(a == b) return;

if(peso[a] > peso[b]) pai[b] = a;

else if(peso[a] < peso[b]) pai[a] = b;

else pai[a] = b, peso[b] ++; 
}

void run(int n)
{
    for(int i = 1; i <= n; i++)
    {
        pai[i] = i;
    }

    for(int i = 1; i < n; i++)
    {
        vector<int> val;

        set<int> inside;

        for(int a = 1;a <= n; a++) inside.insert(Find(a));

        for(auto x: inside) val.push_back(x);

        int ini = 0, fim = val.size() - 1, mid, best = -1, best2 = -1;

        while(fim >= ini)
        {
            mid = (ini + fim)/2;

            int esq[N], idl = 0;

            for(int i = 0; i <= mid; i++) esq[idl] = val[i], idl ++;

            int l = mid + 1, r = val.size() - 1, m, b = -1;

            //cout<<"ESQUERDA "<<mid<<"\n";

            while(r >= l)
            {
                int idr = 0;

                int dir[N];

                m = (l + r)/2;

               // cout<<"DIREITA "<<m<<"\n";

                for(int i = val.size() - 1; i >= m; i--) dir[idr] = val[i], idr ++;

                int Q = query(idl, idr, esq, dir);

                if(Q > 0)
                {
                    b = m;

                    l = m + 1;
                }

                else r = m - 1;
            }

            if(b != -1)
            {
                fim = mid - 1;

                best = mid;

                best2 = b;
            }

            else ini = mid + 1;
        }

       // cout<<best<<" "<<best2<<" "<<val[best]<<" "<<val[best2]<<"\n";

        setRoad(val[best], val[best2]);

        join(val[best], val[best2]);
    }
}

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