oj.uz

Submission #723431

# Submission time Handle Problem Language Result Execution time Memory
723431 2023-04-13T19:31:43 Z tvladm2009 ICC (CEOI16_icc) C++17
100 / 100
 126 ms 612 KB 
#include <bits/stdc++.h>
#include "icc.h"

using namespace std;

typedef long long ll;

const int N_MAX = 100;

vector <int> adj[N_MAX + 2];
vector <int> component[N_MAX + 2];
bool visited[N_MAX + 2];

int cntComp = 0;

void dfs(int u) {
    visited[u] = true;
    component[cntComp].push_back(u);
    for (int v : adj[u]) {
        if (visited[v] == false) {
            dfs(v);
        }
    }
}

int A[N_MAX + 2], B[N_MAX + 2];

void run(int N) {
    for (int t = 1; t < N; t++) {
        int U = 0, V = 0;
        for (int i = 1; i <= N; i++) {
            visited[i] = false;
        }
        for (int i = 1; i <= N; i++) {
            if (visited[i] == 0) {
                cntComp++;
                dfs(i);
            }
        }
        int cntA = 0, cntB = 0;
        for (int bit = 0; bit < 7; bit++) {
            cntA = 0;
            cntB = 0;
            for (int i = 1; i <= cntComp; i++) {
                if ((i >> bit) & 1) {
                    for (int j : component[i]) {
                        A[cntA++] = j;
                    }
                } else {
                    for (int j : component[i]) {
                        B[cntB++] = j;
                    }
                }
            }
            if (query(cntA, cntB, A, B) == true) {
                break;
            }
        }
        int l = 0, r = cntA - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (query(mid - l + 1, cntB, A + l, B) == true) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        U = A[l];
        l = 0;
        r = cntB - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (query(cntA, mid - l + 1, A, B + l) == true) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        V = B[l];
        setRoad(U, V);
        adj[U].push_back(V);
        adj[V].push_back(U);
        for (int i = 1; i <= cntComp; i++) {
            component[i].clear();
        }
        cntComp = 0;
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Ok! 95 queries used.
2 Correct 5 ms 436 KB Ok! 93 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 468 KB Ok! 528 queries used.
2 Correct 35 ms 468 KB Ok! 657 queries used.
3 Correct 30 ms 508 KB Ok! 642 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 500 KB Ok! 1373 queries used.
2 Correct 113 ms 588 KB Ok! 1596 queries used.
3 Correct 105 ms 484 KB Ok! 1596 queries used.
4 Correct 98 ms 612 KB Ok! 1474 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 492 KB Ok! 1464 queries used.
2 Correct 99 ms 496 KB Ok! 1471 queries used.
3 Correct 105 ms 492 KB Ok! 1547 queries used.
4 Correct 94 ms 484 KB Ok! 1489 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 468 KB Ok! 1553 queries used.
2 Correct 107 ms 488 KB Ok! 1521 queries used.
3 Correct 111 ms 468 KB Ok! 1571 queries used.
4 Correct 102 ms 468 KB Ok! 1540 queries used.
5 Correct 97 ms 492 KB Ok! 1455 queries used.
6 Correct 102 ms 492 KB Ok! 1534 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 488 KB Ok! 1544 queries used.
2 Correct 104 ms 492 KB Ok! 1590 queries used.