oj.uz

Submission #443914

# Submission time Handle Problem Language Result Execution time Memory
443914 2021-07-12T11:58:11 Z prvocislo ICC (CEOI16_icc) C++17
100 / 100
 148 ms 960 KB 
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;

const int maxn = 105;
int find_vr(int na, int nb, int a[], int b[])
{
    int lo = 1, hi = na; 
    while (lo < hi)
    {
        int mi = (lo + hi) >> 1;
        int *c = new int[maxn];
        for (int i = 0; i < mi; i++) c[i] = a[i];
        if (query(mi, nb, c, b)) hi = mi;
        else lo = mi+1;
    }
    return a[lo-1]-1;
}
vector<int> c[maxn], g[maxn];
int vis[maxn], a[maxn], b[maxn];
void dfs(int u, int col)
{
    vis[u] = 1, c[col].push_back(u);
    for (int v : g[u]) if (!vis[v]) dfs(v, col);
}
void run(int n)
{
    for (int e = 0; e < n-1; e++)
    {
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < n; i++) c[i].clear();
        int cnt = 0;
        for (int i = 0; i < n; i++) if (!vis[i]) dfs(i, cnt++);
        for (int i = 0; (1 << i) < cnt; i++)
        {
            int na = 0, nb = 0;
            for (int j = 0; j < cnt; j++) 
            {
                if ((1 << i) & j) for (int vr : c[j]) a[na++] = vr+1;
                else for (int vr : c[j]) b[nb++] = vr+1;
            }
            if (query(na, nb, a, b))
            {
                int u = find_vr(na, nb, a, b);
                int v = find_vr(nb, na, b, a);
                g[u].push_back(v), g[v].push_back(u);
                setRoad(u+1, v+1);
                break;
            }
        }
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 460 KB Ok! 95 queries used.
2 Correct 6 ms 460 KB Ok! 98 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 648 KB Ok! 526 queries used.
2 Correct 47 ms 648 KB Ok! 653 queries used.
3 Correct 41 ms 604 KB Ok! 636 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 888 KB Ok! 1379 queries used.
2 Correct 144 ms 956 KB Ok! 1593 queries used.
3 Correct 137 ms 960 KB Ok! 1593 queries used.
4 Correct 148 ms 872 KB Ok! 1481 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 928 KB Ok! 1424 queries used.
2 Correct 130 ms 912 KB Ok! 1452 queries used.
3 Correct 143 ms 852 KB Ok! 1575 queries used.
4 Correct 129 ms 836 KB Ok! 1493 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 880 KB Ok! 1540 queries used.
2 Correct 133 ms 804 KB Ok! 1515 queries used.
3 Correct 141 ms 872 KB Ok! 1573 queries used.
4 Correct 139 ms 900 KB Ok! 1525 queries used.
5 Correct 129 ms 884 KB Ok! 1442 queries used.
6 Correct 135 ms 884 KB Ok! 1478 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 856 KB Ok! 1538 queries used.
2 Correct 146 ms 868 KB Ok! 1588 queries used.