oj.uz

Submission #171815

# Submission time Handle Problem Language Result Execution time Memory
171815 2019-12-30T12:50:13 Z Tuk1352 ICC (CEOI16_icc) C++11
61 / 100
 223 ms 688 KB 
#include <bits/stdc++.h>
#include "icc.h"

using namespace std;

int P[101], S[101];
vector <int> V[101];

int Parent(int a)
{
    if (P[a] == a)
    {
        return a;
    }
    return P[a] = Parent(P[a]);
}

void Union(int a, int b)
{
    int pa, pb;
    pa = Parent(a);
    pb = Parent(b);
    if (pa != pb)
    {
        if (S[pb] > S[pa])
        {
            swap(pa, pb);
        }
        for (int i = 0; i < V[pb].size(); i++)
        {
            V[pa].push_back(V[pb][i]);
        }
        S[pa] += S[pb];
        P[pb] = pa;
    }
}

void run(int N)
{
    srand(time(0));
    for (int i = 0; i <= N; i++)
    {
        P[i] = i;
        S[i] = 1;
        V[i].push_back(i);
    }
    for (int i = N; i >= 2; i--)
    {
        int F[i], k=0;
        for (int y = 0; y < N; y++)
        {
            if (Parent(y) == y)
            {
                F[k] = y;
                k++;
            }
        }
        int A[N], B[N], Pr[k], a, b, sa, sb;
        vector <pair<long long,int>> FF;
        while (true)
        {
            FF.clear();
            for (int y = 0; y < k; y++)
            {
                long long ran = rand()*32768+rand();
                FF.push_back({ran,F[y]});

            }
            //random_shuffle(F, F+k);
            sort(FF.begin(),FF.end());
            sa = 0;
            sb = 0;
            for (int y = 0; y < i/2; y++)
            {
                //A[y] = F[y]+1;
                for (int u = 0; u < V[FF[y].second].size(); u++)
                {
                    A[sa] = V[FF[y].second][u]+1;
                    sa++;
                }
            }
            for (int y = i/2; y < i; y++)
            {
                //B[y-i/2] = F[y]+1;
                for (int u = 0; u < V[FF[y].second].size(); u++)
                {
                    B[sb] = V[FF[y].second][u]+1;
                    sb++;
                }
            }
            if (query(sa, sb, A, B) == 1)
            {
                break;
            }
        }
        int L=0, R=sa, t, s;
        while (R-L > 1)
        {
            t = (L+R) / 2;
            s = (R-1)-t+1;
            int C[s];
            k = 0;
            for (int y = t; y < R; y++)
            {
                C[k] = A[y];
                k++;
            }
            if (query(k, sb, C, B) == 1)
            {
                L = t;
            }
            else
            {
                R = t;
            }
        }
        a = A[L];
        L = 0;
        R = sb;
        while (R-L > 1)
        {
            t = (L+R) / 2;
            s = (R-1)-t+1;
            int C[s];
            k = 0;
            for (int y = t; y < R; y++)
            {
                C[k] = B[y];
                k++;
            }
            if (query(sa, k, A, C) == 1)
            {
                L = t;
            }
            else
            {
                R = t;
            }
        }
        b = B[L];
        setRoad(a, b);
        Union(a-1, b-1);
    }
}

Compilation message

icc.cpp: In function 'void Union(int, int)':
icc.cpp:29:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < V[pb].size(); i++)
                         ~~^~~~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:76:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int u = 0; u < V[FF[y].second].size(); u++)
                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~
icc.cpp:85:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int u = 0; u < V[FF[y].second].size(); u++)
                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~
icc.cpp:58:25: warning: unused variable 'Pr' [-Wunused-variable]
         int A[N], B[N], Pr[k], a, b, sa, sb;
                         ^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Ok! 100 queries used.
2 Correct 9 ms 632 KB Ok! 106 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 564 KB Ok! 531 queries used.
2 Correct 63 ms 504 KB Ok! 807 queries used.
3 Correct 64 ms 564 KB Ok! 800 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 688 KB Ok! 1522 queries used.
2 Correct 223 ms 564 KB Ok! 2119 queries used.
3 Correct 172 ms 504 KB Ok! 1705 queries used.
4 Correct 178 ms 632 KB Ok! 1722 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 572 KB Ok! 1555 queries used.
2 Correct 166 ms 632 KB Ok! 1616 queries used.
3 Correct 180 ms 564 KB Ok! 1774 queries used.
4 Correct 173 ms 632 KB Ok! 1624 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 197 ms 504 KB Too many queries! 1863 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 188 ms 504 KB Too many queries! 1819 out of 1625
2 Halted 0 ms 0 KB -