oj.uz

Submission #919246

# Submission time Handle Problem Language Result Execution time Memory
919246 2024-01-31T13:27:05 Z aykhn ICC (CEOI16_icc) C++17
100 / 100
 100 ms 860 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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Ok! 100 queries used.
2 Correct 4 ms 600 KB Ok! 99 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 600 KB Ok! 534 queries used.
2 Correct 28 ms 600 KB Ok! 645 queries used.
3 Correct 27 ms 600 KB Ok! 654 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 616 KB Ok! 1391 queries used.
2 Correct 96 ms 600 KB Ok! 1613 queries used.
3 Correct 86 ms 600 KB Ok! 1600 queries used.
4 Correct 77 ms 600 KB Ok! 1485 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 636 KB Ok! 1484 queries used.
2 Correct 77 ms 612 KB Ok! 1478 queries used.
3 Correct 83 ms 632 KB Ok! 1616 queries used.
4 Correct 79 ms 600 KB Ok! 1452 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 600 KB Ok! 1609 queries used.
2 Correct 90 ms 860 KB Ok! 1597 queries used.
3 Correct 90 ms 600 KB Ok! 1613 queries used.
4 Correct 87 ms 600 KB Ok! 1596 queries used.
5 Correct 78 ms 612 KB Ok! 1425 queries used.
6 Correct 81 ms 628 KB Ok! 1536 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 600 KB Ok! 1602 queries used.
2 Correct 100 ms 600 KB Ok! 1610 queries used.