oj.uz

답안 #171825

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
171825 2019-12-30T12:59:22 Z Tuk1352 CEOI16_icc (CEOI16_icc) C++11
61 / 100
 214 ms 632 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);
    }
    int q = 0;
    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()*RAND_MAX+rand();
                FF.push_back({ran,F[y]});

            }
            //random_shuffle(F, F+k);
            //sort(FF.begin(),FF.end());
            random_shuffle(FF.begin(),FF.end());
            sa = 0;
            sb = 0;
            for (int y = 0; y < k/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 = k/2; y < k; 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:78:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int u = 0; u < V[FF[y].second].size(); u++)
                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~
icc.cpp:87:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int u = 0; u < V[FF[y].second].size(); u++)
                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~
icc.cpp:59:25: warning: unused variable 'Pr' [-Wunused-variable]
         int A[N], B[N], Pr[k], a, b, sa, sb;
                         ^~
icc.cpp:47:9: warning: unused variable 'q' [-Wunused-variable]
     int q = 0;
         ^

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 504 KB Ok! 99 queries used.
2 Correct 9 ms 504 KB Ok! 104 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 504 KB Ok! 526 queries used.
2 Correct 65 ms 560 KB Ok! 849 queries used.
3 Correct 62 ms 504 KB Ok! 784 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 560 KB Ok! 1487 queries used.
2 Correct 214 ms 632 KB Ok! 2119 queries used.
3 Correct 166 ms 504 KB Ok! 1717 queries used.
4 Correct 168 ms 504 KB Ok! 1715 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 156 ms 504 KB Ok! 1574 queries used.
2 Correct 155 ms 560 KB Ok! 1566 queries used.
3 Correct 182 ms 564 KB Ok! 1842 queries used.
4 Correct 159 ms 632 KB Ok! 1609 queries used.

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 186 ms 504 KB Too many queries! 1865 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 183 ms 508 KB Too many queries! 1853 out of 1625
2 Halted 0 ms 0 KB -