oj.uz

답안 #919250

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
919250 2024-01-31T13:28:42 Z vjudge1 CEOI16_icc (CEOI16_icc) C++17
100 / 100
 89 ms 856 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++)
        {
            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]);//
    }
}

Compilation message

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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 600 KB Ok! 102 queries used.
2 Correct 4 ms 600 KB Ok! 100 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 600 KB Ok! 524 queries used.
2 Correct 28 ms 600 KB Ok! 651 queries used.
3 Correct 27 ms 600 KB Ok! 659 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 600 KB Ok! 1373 queries used.
2 Correct 86 ms 600 KB Ok! 1610 queries used.
3 Correct 83 ms 600 KB Ok! 1612 queries used.
4 Correct 82 ms 856 KB Ok! 1478 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 600 KB Ok! 1502 queries used.
2 Correct 77 ms 600 KB Ok! 1482 queries used.
3 Correct 84 ms 600 KB Ok! 1599 queries used.
4 Correct 75 ms 636 KB Ok! 1454 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 600 KB Ok! 1590 queries used.
2 Correct 84 ms 600 KB Ok! 1585 queries used.
3 Correct 87 ms 800 KB Ok! 1621 queries used.
4 Correct 83 ms 852 KB Ok! 1561 queries used.
5 Correct 75 ms 600 KB Ok! 1446 queries used.
6 Correct 84 ms 620 KB Ok! 1543 queries used.

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 620 KB Ok! 1609 queries used.
2 Correct 89 ms 612 KB Ok! 1612 queries used.