oj.uz

답안 #919241

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
919241 2024-01-31T13:23:40 Z aykhn CEOI16_icc (CEOI16_icc) C++17
0 / 100
 3 ms 600 KB 
#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++)
        {
            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]);
    }
}

Compilation message

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

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 600 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 600 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 600 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 600 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 600 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 600 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -