제출 #171818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
171818		Tuk1352	ICC (CEOI16_icc)	C++11	61 / 100	214 ms	636 KiB

icc

#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()*RAND_MAX+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);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10