Submission #1117020

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1117020	2024-11-22T18:40:52 Z	mmk	ICC (CEOI16_icc)	C++14	40 / 100	334 ms	1272 KB

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

const int MAXN = 110;

int pai[MAXN], marc[MAXN], sz[MAXN];
map<pair<int,int>,bool> aresta;

// int query(int sza, int szb, int a[], int b[]);
// int setRoad(int a, int b);

// srand(time(0));
int q(vector<int> a, vector<int> b)
{
    if(a.size() == 0 || b.size() == 0) return false;

    int sza = a.size(), szb = b.size();

    for(int v : a)
    {
        for(int viz : b)
            if(aresta[{v,viz}]) return 1;
    }

    int novoA[sza], novoB[szb];
    for(int i = 0; i < sza; i++)
        novoA[i] = a[i];
    for(int i = 0; i < szb; i++)
        novoB[i] = b[i];

    return query(sza, szb, novoA, novoB);
}

int find(int v)
{
    if(pai[v] == v) return v;
    return pai[v] = find(pai[v]);
}

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

    if(a == b) return;

    if(sz[a] < sz[b]) swap(a,b);

    pai[b] = a;
    sz[a] += sz[b];
}

vector<int> botaGrupo(int v, int N)
{
    vector<int> grupo;
    for(int i = 1; i <= N; i++)
    {
        if(find(i) == find(v))
            grupo.push_back(i);
    }

    return grupo;
}

pair<vector<int>,vector<int>> split(vector<int> v, int N)
{
    int sz = v.size();
    int qtdA = 0, qtdB = 0;
    for(int i = 1; i <= N; i++)
        marc[i] = 0;

    vector<int> a,b;

    for(int i = 0; i < sz; i++)
    {
        if(marc[v[i]]) continue;
        int grupo = rand()%2;

        vector<int> adiciona = botaGrupo(v[i],N);
        if(qtdA >= sz/2)
        {
            for(int cur : adiciona)
            {
                marc[cur] = 1;
                b.push_back(cur);
            }
            qtdB++;
        }
        else if(qtdB >= sz/2)
        {
            for(int cur : adiciona)
            {
                marc[cur] = 1;
                a.push_back(cur);
            }
            qtdA++;
        }
        else
        {
            for(int cur : adiciona)
            {
                marc[cur] = 1;
                if(grupo == 0) a.push_back(cur);
                else b.push_back(cur);
            }
            if(grupo == 0) qtdA++;
            else qtdB++;
        }
    }
    return make_pair(a,b);
}

pair<vector<int>,vector<int>> split2(vector<int> v, int N)
{
    int sz = v.size();
    int qtdA = 0, qtdB = 0;

    vector<int> a,b;

    for(int i = 0; i < sz; i++)
    {
        int grupo = rand()%2;
        int cur = v[i];

        if(qtdA >= sz/2)
        {
            b.push_back(cur);
            qtdB++;
        }
        else if(qtdB >= sz/2)
        {
            a.push_back(cur);
            qtdB++;
        }
        else
        {
            if(grupo == 0) a.push_back(cur);
            else b.push_back(cur);
            if(grupo == 0) qtdA++;
            else qtdB++;
        }
    }

    return make_pair(a,b);
}

pair<vector<int>,vector<int>> achaAresta(int N)
{
    vector<int> todos;
    for(int i = 1; i <= N; i++)
        todos.push_back(i);

    pair<vector<int>,vector<int>> temp = split(todos,N);
    vector<int> a,b;
    a = temp.first, b = temp.second;

    // cerr << "grupo1: ";
    // for(int cur : a) cerr << cur << " ";
    // cerr << "\n";
    // cerr << "grupo2: ";
    // for(int cur : b) cerr << cur << " ";
    // cerr << "\n";

    vector<int> aux;

    if(q(a,b)) return {a,b};
    else return {aux,aux};
}

vector<int> achaGrupoPonta(vector<int> a, vector<int> b, int N)
{
    vector<int> nulo;
    if(a.size() == 0 || b.size() == 0)
        return nulo;

    int grupoA = find(a[0]);
    bool mesmo = true;
    for(int cur : a)
    {
        if(find(cur) != grupoA)
            mesmo = false;
    }
    if(mesmo)
        return a;

    vector<int> half1, half2;

    pair<vector<int>,vector<int>> temp = split(a,N);

    half1 = temp.first, half2 = temp.second;

    if(q(half1,b))
        return achaGrupoPonta(half1,b,N);
    else
        return achaGrupoPonta(half2,b,N);
}

int achaPonta(vector<int> a, vector<int> b, int N)
{
    if(a.size() == 0)
        return -1;
    if(a.size() == 1)
        return a[0];

    vector<int> half1,half2;
    pair<vector<int>,vector<int>> temp = split2(a,N);
    half1 = temp.first, half2 = temp.second;

    if(q(half1,b)) return achaPonta(half1,b,N);
    return achaPonta(half2,b,N);
}

void run(int N)
{
    int cnt = N - 1;

    for(int i = 1; i <= N; i++)
    {
        pai[i] = i;
        sz[i] = 1;
    }

    while(cnt--)
    {
        bool achou = false;
        pair<vector<int>,vector<int>> aux;
        while(!achou)
        {
            // cerr << "bonga\n";
            aux = achaAresta(N);

            if(aux.first.size() == 0 && aux.second.size() == 0)
                continue;
            else
                achou = true;
        }

        vector<int> grupoA = achaGrupoPonta(aux.first,aux.second,N);
        vector<int> grupoB = achaGrupoPonta(aux.second,aux.first,N);

        int pontaA = achaPonta(grupoA,grupoB,N);
        int pontaB = achaPonta(grupoB,grupoA,N);

        setRoad(pontaA,pontaB);
        un(pontaA,pontaB);
        aresta[{pontaA,pontaB}] = 1;
        aresta[{pontaB,pontaA}] = 1;
    }
}

Subtask #1
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	592 KB	Ok! 120 queries used.
2	Correct	6 ms	764 KB	Ok! 132 queries used.

Subtask #2
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	592 KB	Ok! 701 queries used.
2	Correct	60 ms	760 KB	Ok! 908 queries used.
3	Correct	54 ms	796 KB	Ok! 887 queries used.

Subtask #3
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	190 ms	1272 KB	Ok! 1891 queries used.
2	Correct	334 ms	1104 KB	Ok! 2218 queries used.
3	Correct	232 ms	1104 KB	Ok! 2107 queries used.
4	Correct	234 ms	1104 KB	Ok! 2074 queries used.