oj.uz

Submission #1076812

# Submission time Handle Problem Language Result Execution time Memory
1076812 2024-08-26T16:49:24 Z vjudge1 ICC (CEOI16_icc) C++17
100 / 100
 98 ms 632 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

#define isz(a) (int)(a).size()

const int NM = 100;

int parent[NM+5], sz[NM+5], id[NM+5], k;
vector <int> arr[NM+5];
vector <int> f, g;
int _X[NM+5], _Y[NM+5];

void make_set(int v){
    parent[v] = v;
    sz[v] = 1;
    arr[v] = {v};
}

int find_set(int v){
    return parent[v] == v ? v : parent[v] = find_set(parent[v]);
}

void union_sets(int u, int v){
    u = find_set(u);
    v = find_set(v);
    if (u == v) return;
    if (sz[u] < sz[v]) swap(u, v);
    parent[v] = u;
    sz[u] += sz[v];
    for (int x : arr[v]) arr[u].push_back(x);
    arr[v].clear();
}

int ask(vector <int> &X, vector <int> &Y){
	for (int i = 0; i < isz(X); i++) _X[i] = X[i];
	for (int i = 0; i < isz(Y); i++) _Y[i] = Y[i];
	return query(isz(X), isz(Y), _X, _Y);
}

void guess(int u, int v){
	setRoad(u, v);
}

void run(int n){
    for (int i = 1; i <= n; i++) make_set(i);
    for (int i = 1; i < n; i++){
        k = 0;
        for (int j = 1; j <= n; j++)
            if (parent[j] == j) id[k++] = j;
        
        int s = 0;
        for (int b = 0; b <= __lg(k-1); b++){
            vector <int> X = {}, Y = {};
            for (int j = 0; j < k; j++)
                for (int v : arr[id[j]])
                    if ((j>>b)&1) X.push_back(v); else Y.push_back(v);
            if (ask(X, Y)) s ^= (1<<b);
        }
        f.clear();
        g.clear();
        for (int u = 0; u < k; u++){
            int v = u^s;
            if (u < v && v < k){
                f.push_back(u);
                g.push_back(v);
            }
        }
        int l = 0, r = isz(f)-2, res = isz(f)-1;
        while (l <= r){
            int mid = (l+r)/2;
            vector <int> X = {}, Y = {};
            for (int j = 0; j <= mid; j++){
                for (int v : arr[id[f[j]]]) X.push_back(v);
                for (int v : arr[id[g[j]]]) Y.push_back(v);
            }
            if (ask(X, Y)){
                res = mid;
                r = mid-1;
            }
            else l = mid+1;
        }
        int resf = isz(arr[id[f[res]]])-1, resg = isz(arr[id[g[res]]])-1;
        l = 0, r = resf-1;
        while (l <= r){
            int mid = (l+r)/2;
            vector <int> X = {}, Y = arr[id[g[res]]];
            for (int j = 0; j <= mid; j++)
                X.push_back(arr[id[f[res]]][j]);
            if (ask(X, Y)){
                resf = mid;
                r = mid-1;
            }
            else l = mid+1;
        }
        l = 0, r = resg-1;
        while (l <= r){
            int mid = (l+r)/2;
            vector <int> X = arr[id[f[res]]], Y = {};
            for (int j = 0; j <= mid; j++)
                Y.push_back(arr[id[g[res]]][j]);
            if (ask(X, Y)){
                resg = mid;
                r = mid-1;
            }
            else l = mid+1;
        }
        int u = arr[id[f[res]]][resf], v = arr[id[g[res]]][resg];
        guess(u, v);
        union_sets(u, v);
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 600 KB Ok! 110 queries used.
2 Correct 5 ms 632 KB Ok! 108 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 600 KB Ok! 611 queries used.
2 Correct 23 ms 604 KB Ok! 504 queries used.
3 Correct 24 ms 612 KB Ok! 539 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 600 KB Ok! 1515 queries used.
2 Correct 70 ms 620 KB Ok! 1206 queries used.
3 Correct 83 ms 604 KB Ok! 1539 queries used.
4 Correct 84 ms 616 KB Ok! 1509 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 604 KB Ok! 1515 queries used.
2 Correct 83 ms 600 KB Ok! 1516 queries used.
3 Correct 82 ms 604 KB Ok! 1488 queries used.
4 Correct 88 ms 604 KB Ok! 1534 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 604 KB Ok! 1456 queries used.
2 Correct 82 ms 600 KB Ok! 1506 queries used.
3 Correct 76 ms 600 KB Ok! 1356 queries used.
4 Correct 93 ms 604 KB Ok! 1519 queries used.
5 Correct 85 ms 604 KB Ok! 1528 queries used.
6 Correct 84 ms 604 KB Ok! 1533 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 604 KB Ok! 1376 queries used.
2 Correct 71 ms 620 KB Ok! 1270 queries used.