제출 #919246

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
919246		aykhn	ICC (CEOI16_icc)	C++17	100 / 100	100 ms	860 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"

// author: aykhn

using namespace std;

struct DSU
{
    vector<vector<int>> id;
    vector<int> e;
    void init(int n)
    {
        id.resize(n + 1);
        for (int i = 1; i <= n; i++) id[i].push_back(i);
        e.assign(n + 1, -1);
    }
    int get(int x)
    {
        if (e[x] < 0) return x;
        return e[x] = get(e[x]);
    }
    void unite(int x, int y)
    {
        x = get(x), y = get(y);
        if (x == y) return;
        if (e[x] > e[y]) swap(x, y);
        for (int z : id[y]) id[x].push_back(z);
        id[y].clear();
        e[x] += e[y];
        e[y] = x;
    }
};

void run(int n)
{
    srand(time(0));
    DSU dsu;
    dsu.init(n);
    for (int C = 1; C < n; C++)
    {
        vector<int> v;
        for (int i = 1; i <= n; i++) if (dsu.get(i) == i) v.push_back(i);
        random_shuffle(v.begin(), v.end());
        int val = 0;
        vector<int> a[2];
        for (int lg = 0; lg < 7; lg++)
        {
            a[0].clear(), a[1].clear();
            for (int i = 0; i < v.size(); i++)
            {
                for (int z : dsu.id[v[i]]) a[i >> lg & 1].push_back(z);
            }
            if (query(a[0].size(), a[1].size(), a[0].data(), a[1].data())) break;
        }
        int l = 0;
        int r = (int)a[0].size() - 1;
        while (l < r)
        {
            int mid = (l + r) >> 1;
            vector<int> x, y;
            for (int i = l; i <= mid; i++) x.push_back(a[0][i]);
            for (int i = mid + 1; i <= r; i++) y.push_back(a[0][i]);
            if (query(a[1].size(), x.size(), a[1].data(), x.data()))
            {
                a[0] = x;
                r = mid;
            }
            else
            {
                a[0] = y;
                l = mid + 1;
            }
        }
        l = 0;
        r = (int)a[1].size() - 1;
        while (l < r)
        {
            int mid = (l + r) >> 1;
            vector<int> x, y;
            for (int i = l; i <= mid; i++) x.push_back(a[1][i]);
            for (int i = mid + 1; i <= r; i++) y.push_back(a[1][i]);
            if (query(a[0].size(), x.size(), a[0].data(), x.data()))
            {
                a[1] = x;
                r = mid;
            }
            else
            {
                a[1] = y;
                l = mid + 1;
            }
        }
        dsu.unite(a[0][0], a[1][0]);
        setRoad(a[0][0], a[1][0]);
    }
}

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

icc.cpp: In function 'void run(int)':
icc.cpp:50:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             for (int i = 0; i < v.size(); i++)
      |                             ~~^~~~~~~~~~
icc.cpp:45:13: warning: unused variable 'val' [-Wunused-variable]
   45 |         int val = 0;
      |             ^~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10