oj.uz

Submission #919251

# Submission time Handle Problem Language Result Execution time Memory
919251 2024-01-31T13:29:48 Z aykhn ICC (CEOI16_icc) C++17
90 / 100
 95 ms 848 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)
{
    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: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:44:13: warning: unused variable 'val' [-Wunused-variable]
   44 |         int val = 0;
      |             ^~~

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 600 KB Ok! 526 queries used.
2 Correct 28 ms 600 KB Ok! 641 queries used.
3 Correct 26 ms 600 KB Ok! 636 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 600 KB Ok! 1405 queries used.
2 Correct 86 ms 616 KB Ok! 1626 queries used.
3 Correct 85 ms 612 KB Ok! 1615 queries used.
4 Correct 82 ms 848 KB Ok! 1505 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 616 KB Ok! 1483 queries used.
2 Correct 75 ms 600 KB Ok! 1480 queries used.
3 Correct 83 ms 600 KB Ok! 1610 queries used.
4 Correct 77 ms 848 KB Ok! 1501 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 600 KB Ok! 1584 queries used.
2 Correct 88 ms 600 KB Ok! 1600 queries used.
3 Correct 83 ms 620 KB Ok! 1624 queries used.
4 Correct 95 ms 600 KB Ok! 1580 queries used.
5 Correct 76 ms 848 KB Ok! 1470 queries used.
6 Correct 79 ms 600 KB Ok! 1540 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 616 KB Ok! 1596 queries used.
2 Incorrect 85 ms 600 KB Too many queries! 1633 out of 1625
3 Halted 0 ms 0 KB -