oj.uz

Submission #58051

# Submission time Handle Problem Language Result Execution time Memory
58051 2018-07-16T16:27:05 Z MatheusLealV ICC (CEOI16_icc) C++17
0 / 100
 4 ms 776 KB 
#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.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 29.0

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

Subtask #6
0 / 10.0

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