Submission #723431

#	Time	Username	Problem	Language	Result	Execution time	Memory
723431		tvladm2009	ICC (CEOI16_icc)	C++17	100 / 100	126 ms	612 KiB

icc

#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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10