Submission #1226848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226848		LucaIlie	Sphinx's Riddle (IOI24_sphinx)	C++20	12 / 100	42 ms	1204 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 250;
int n, m;
int vert;
int parent[MAX_N];
vector<int> adj[MAX_N];
mt19937 rnd(1010);

int findParent(int v) {
    if (parent[v] != v)
        parent[v] = findParent(parent[v]);
    return parent[v];
}

void unionn(int u, int v) {
    // printf("UNESC %d %d\n", u, v);
    u = findParent(u);
    v = findParent(v);
    if (u == v)
        return;
    parent[u] = v;
}

int ask(vector<int> v) {
    vector<int> e(n, n);
    for (int i: v)
        e[i] = -1;
    e[vert] = -1;
    int a = perform_experiment(e);
    for (int i: v)
        e[i] = 0;
    e[vert] = 0;
    int b = perform_experiment(e);
    return v.size() - a + b;
}


void divide(vector<int> cand, int c) {
    shuffle(cand.begin(), cand.end(), rnd);
    int n = cand.size();

    if (n == 0)
        return;

    if (c == -1)
        c = ask(cand);

    if (c == 0)
        return;

    if (n == 1) {
        unionn(vert, cand[0]);
        return;
    }

    vector<int> a, b;
    for (int i = 0; i < n / 2; i++)
        a.push_back(cand[i]);
    for (int i = n / 2; i < n; i++)
        b.push_back(cand[i]);

    int aa = ask(a);
    int bb = c - aa;
    if (aa > 0)
        divide(a, aa);
    if (bb > 0)
        divide(b, bb);
}

vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
    n = N;
    m = X.size();
    for (int i = 0; i < m; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }

    for (int v = 0; v < n; v++)
        parent[v] = v;

    for (int v = 1; v < n; v++) {
        vector<int> cand;
        for (int u: adj[v]) {
            if (u < v)
                cand.push_back(findParent(u));
        }
        sort(cand.begin(), cand.end());
        cand.resize(unique(cand.begin(), cand.end()) - cand.begin());

        // printf("CAND ");
        // for (int u: cand)
        //     printf("%d ", u);
        // printf("\n");

        vert = v;
        divide(cand, -1);
    }

    vector<int> ans(n);
    for (int v = 0; v < n; v++)
        ans[v] = findParent(v);
    return ans;
}

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