oj.uz

Submission #1117185

# Submission time Handle Problem Language Result Execution time Memory
1117185 2024-11-22T21:34:59 Z mmk ICC (CEOI16_icc) C++14
0 / 100
 271 ms 1260 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;
    }

    bool jahTem = false;
    int rep = 0;
    while(cnt--)
    {
        bool achou = false;
        pair<vector<int>,vector<int>> aux;


        for(int i = 1; i <= N; i++)
        {
            int aux = find(i);
            if(sz[i] > N/2)
            {
                jahTem = true;
                rep = aux;
            }
        }

        while(!achou && !jahTem)
        {
            // cerr << "bonga\n";
            aux = achaAresta(N);

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

        if(jahTem)
        {
            aux.first = botaGrupo(rep,N);

            for(int i = 1; i <= N; i++)
            {
                if(find(i) != find(rep))
                    aux.second.push_back(i);
            }
        }

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

        int pontaA = achaPonta(aux.first,aux.second,N);
        int pontaB = achaPonta(aux.second,aux.first,N);

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 592 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 592 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 162 ms 1260 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 1104 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 200 ms 1104 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 271 ms 1256 KB Wrong road!
2 Halted 0 ms 0 KB -