제출 #1307983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307983		regulardude6	스핑크스 (IOI24_sphinx)	C++20	100 / 100	339 ms	4144 KiB

sphinx

#include <bits/stdc++.h>
#include "sphinx.h"
using namespace std;

static int N;
static int p[250];
static vector<int> edge[250];
static vector<int> ord;
static bool reached[250];
static set<int> unchecked_set;
static bool keepv[250];
static set<int> ccEdge[250];
static set<int> ccset;
static int parityv[250];

static int where(int x) {
    if (p[x] < 0) return x;
    return (p[x] = where(p[x]));
}

static int color_id(int x) {
    return (ord[x] >= 0 ? ord[x] + N : where(x));
}

static void dfs(int x) {
    reached[x] = true;
    for (int i : edge[x]) {
        if (!reached[i] && color_id(x) == color_id(i)) dfs(i);
    }
}

static int expected() {
    for (int i = 0; i < N; i++) reached[i] = false;
    int sum = 0;
    for (int i = 0; i < N; i++) {
        if (!reached[i]) {
            sum++;
            dfs(i);
        }
    }
    return sum;
}

static void pDfs(int x) {
    reached[x] = true;
    for (int i : ccEdge[x]) {
        if (!reached[i]) {
            parityv[i] = 1 - parityv[x];
            pDfs(i);
        }
    }
}

vector<int> find_colours(int NN, vector<int> X, vector<int> Y) {
    N = NN;

    ord.assign(N, -1);
    for (int i = 0; i < 250; i++) {
        edge[i].clear();
        ccEdge[i].clear();
        reached[i] = false;
        parityv[i] = 0;
        keepv[i] = false;
        p[i] = -1;
    }
    unchecked_set.clear();
    ccset.clear();

    int M = (int)X.size();
    for (int i = 0; i < M; i++) {
        edge[Y[i]].push_back(X[i]);
        edge[X[i]].push_back(Y[i]);
    }

    for (int i = 1; i < N; i++) {
        while (true) {
            for (int j = 0; j <= i; j++) ord[j] = -1;
            for (int j = i + 1; j < N; j++) ord[j] = N;
            if (perform_experiment(ord) == expected()) break;

            unchecked_set.clear();
            for (int j = 0; j < i; j++) {
                if (where(j) != i) unchecked_set.insert(where(j));
            }

            vector<int> vec;
            vec.reserve(unchecked_set.size());
            for (int j : unchecked_set) vec.push_back(j);

            int a = 0, b = (int)vec.size() - 1;
            while (a != b) {
                int half = (a + b) / 2;
                for (int j = 0; j < N; j++) keepv[j] = false;
                for (int j = a; j <= half; j++) keepv[vec[j]] = true;

                for (int j = 0; j < i; j++) {
                    if (keepv[where(j)]) ord[j] = -1;
                    else ord[j] = N;
                }
                ord[i] = -1;
                for (int j = i + 1; j < N; j++) ord[j] = N;

                if (perform_experiment(ord) == expected()) a = half + 1;
                else b = half;
            }
            p[where(vec[a])] = i;
        }
    }

    for (int i = 0; i < N; i++) ccset.insert(where(i));

    vector<int> F(N, -1);

    if (ccset.size() == 1) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) ord[j] = -1;
            ord[0] = i;
            if (perform_experiment(ord) == 1) {
                for (int j = 0; j < N; j++) F[j] = i;
                break;
            }
        }
    } else {
        for (int i = 0; i < N; i++) {
            for (int j : edge[i]) {
                int a = where(i), b = where(j);
                if (a != b) {
                    ccEdge[a].insert(b);
                    ccEdge[b].insert(a);
                }
            }
        }

        for (int i = 0; i < N; i++) reached[i] = false;
        int root = *ccset.begin();
        parityv[root] = 0;
        pDfs(root);

        for (int par = 0; par < 2; par++) {
            for (int i = 0; i < N; i++) {
                while (true) {
                    for (int j = 0; j < N; j++) {
                        int w = where(j);
                        if (parityv[w] == par || F[w] != -1) ord[j] = i;
                        else ord[j] = -1;
                    }

                    if (perform_experiment(ord) == expected()) break;

                    unchecked_set.clear();
                    for (int j = 0; j < N; j++) {
                        int w = where(j);
                        if (parityv[w] == 1 - par && F[w] == -1) unchecked_set.insert(w);
                    }

                    vector<int> vec;
                    vec.reserve(unchecked_set.size());
                    for (int j : unchecked_set) vec.push_back(j);

                    int a = 0, b = (int)vec.size() - 1;
                    while (a != b) {
                        int half = (a + b) / 2;
                        for (int j = 0; j < N; j++) keepv[j] = false;
                        for (int j = a; j <= half; j++) {
                            if (F[vec[j]] == -1) keepv[vec[j]] = true;
                        }

                        for (int j = 0; j < N; j++) {
                            if (keepv[where(j)]) ord[j] = -1;
                            else ord[j] = i;
                        }

                        if (perform_experiment(ord) == expected()) a = half + 1;
                        else b = half;
                    }
                    F[where(vec[a])] = i;
                }
            }
        }

        for (int i = 0; i < N; i++) F[i] = F[where(i)];
    }

    return F;
}

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 7 / 7
• Subtask 3: 33 / 33
• Subtask 4: 21 / 21
• Subtask 5: 36 / 36