Submission #1227517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227517		LucaIlie	Sphinx's Riddle (IOI24_sphinx)	C++20	64 / 100	269 ms	1728 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];
int depth[MAX_N];
bool vis[MAX_N];
int finalColor[MAX_N];
vector<int> adj[MAX_N];
vector<int> adjComp[MAX_N];
vector<int> comp[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) {
    u = findParent(u);
    v = findParent(v);
    if (u == v)
        return;
    parent[u] = v;
}

int totalComp;
int E[MAX_N];
void dfsComp(int u, int t) {
    vis[u] = true;
    vector<int> adjj = (t == 1 ? adjComp[u] : adj[u]);
    for (int v: adjj) {
        if (vis[v] || E[u] != E[v])
            continue;
        dfsComp(v, t);
    }
}

void findComp(vector<int> e, int t) {
    for (int v = 0; v < n; v++) {
        E[v] = e[v];
        vis[v] = false;
    }
    totalComp = 0;
    for (int v = 0; v < n; v++) {
        if (t == 1 && findParent(v) != v)
            continue;
        if (vis[v])
            continue;

        totalComp++;
        if (e[v] == -1) 
            continue;
        dfsComp(v, t);
    }
    for (int v = 0; v < n; v++) {
        E[v] = 0;
        vis[v] = false;
    }
}


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;
    findComp(e, 0);
    // int b = perform_experiment(e);
    int b = totalComp;
    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);
}

void findSpan(int u) {
    vis[u] = true;
    for (int v: adjComp[u]) {
        if (vis[v])
            continue;
        depth[v] = depth[u] + 1;
        findSpan(v);
    }
}


int color;
vector<int> fixedC;
int ask2(vector<int> v) {
    vector<int> e(n, n);
    for (int i: fixedC) {
        for (int v: comp[i])
            e[v] = color;
    }
    for (int i: v) {
        for (int v: comp[i])
            e[v] = -1;
    }
    int a = perform_experiment(e);
    findComp(e, 1);
    return totalComp - a;
}

vector<int> stripRange(int l, int r, vector<int> v) {
    vector<int> w;
    for (int i = l; i <= r; i++)
        w.push_back(v[i]);
    return w;
}

void divide3(vector<int> cand, int ans) {
    shuffle(cand.begin(), cand.end(), rnd);
    int i = 0;
    while (i < (int)cand.size()) {
        int a = ask2(stripRange(i, cand.size() - 1, cand));
        if (a == 0)
            break;
        int l = i - 1, r = cand.size();
        while (r - l > 1) {
            int mid = (l + r) / 2;
            int a = ask2(stripRange(i, mid, cand));
            if (a > 0)
                r = mid;
            else
                l = mid;
        }
        if (r < (int)cand.size())
            finalColor[cand[r]] = color;
        i = r + 1;
    }
}

void divide2(vector<int> cand, int ans) {
    shuffle(cand.begin(), cand.end(), rnd);
    int n = cand.size();
    if (n == 0)
        return;

    if (ask2(cand) == 0)
        return;

    int bs = n;
    for (int i = 0; i < (int)cand.size(); i += bs) {
        vector<int> cand2;
        for (int j = i; j < (int)cand.size() && j < i + bs; j++)
            cand2.push_back(cand[j]);
        divide3(cand2, -1);
    }
}

void findColors(int c, int p) {
    vector<int> cand;
    fixedC.clear();
    color = c;
    for (int v = 0; v < n; v++) {
        if (findParent(v) != v)
            continue;

        if (depth[v] % 2 == p && finalColor[v] == -1)
            cand.push_back(v);
        else if (depth[v] % 2 != p)
            fixedC.push_back(v);
    }

    divide2(cand, -1);
}

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;

    vector<int> perm(n);
    for (int i = 0; i < n; i++) 
        perm[i] = i;
    // shuffle(perm.begin(), next(next(perm.begin())), rnd);
    vector<bool> used(n, false);
    used[perm[0]] = true;
    for (int i = 1; i < n; i++) {
        int v = perm[i];
        used[v] = true;
        vector<int> cand;
        set<int> s;
        for (int u: adj[v]) {
            if (used[u]) {
                if (s.find(findParent(u)) == s.end()) { 
                    s.insert(findParent(u));
                    cand.push_back(u);
                }
            }
        }
        vert = v;
        divide(cand, -1);
    }

    for (int v = 0; v < n; v++) {
        comp[findParent(v)].push_back(v);
        for (int u: adj[v]) 
            adjComp[findParent(v)].push_back(findParent(u));
    }
    totalComp = 0;
    for (int v = 0; v < n; v++) {
        if (findParent(v) != v)
            continue;
        totalComp++;
        finalColor[v] = -1;
        sort(adjComp[v].begin(), adjComp[v].end());
        adjComp[v].resize(unique(adjComp[v].begin(), adjComp[v].end()) - adjComp[v].begin());
    }

    int tc = totalComp;
    if (totalComp == 1) {
        vector<int> e(n, -1);
        for (int c = 0; c < n; c++) {
            e[0] = c; 
            if (perform_experiment(e) == 1) {
                finalColor[findParent(0)] = c;
                break;
            }
        }
    } else {
        findSpan(0);
        shuffle(perm.begin(), perm.end(), rnd);
        for (int i = 0; i < n; i++) {
            int c = perm[i];
            findColors(c, 0);
            findColors(c, 1);
        }
    }

    
    vector<int> ans(n);
    for (int v = 0; v < n; v++)
        ans[v] = finalColor[findParent(v)];
    for (int v = 0; v < n; v++) {
        if (finalColor[v] == -1)
            ans.resize(tc);
    }
    return ans;
}

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