Submission #1241885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241885		Account	Sphinx's Riddle (IOI24_sphinx)	C++20	0 / 100	0 ms	412 KiB

sphinx

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

int N; 
vector<int> C; 
vector<vector<int>> adj; 
int calls_cnt = 0;
const int CALLS_CNT_LIMIT = 2750;

int count_components(const vector<int>& S) {
    int components_cnt = 0;
    vector<bool> vis(N, false);
    for (int i = 0; i < N; i++) {
        if (vis[i]) continue;
        components_cnt++;
        queue<int> q;
        q.push(i);
        vis[i] = true;
        while (!q.empty()) {
            int cur = q.front(); q.pop();
            for (int nxt : adj[cur]) {
                if (!vis[nxt] && S[nxt] == S[cur]) {
                    vis[nxt] = true;
                    q.push(nxt);
                }
            }
        }
    }
    return components_cnt;
}

int perform_experiment(const vector<int>& E) {
    calls_cnt++;
    if (calls_cnt > CALLS_CNT_LIMIT) {
        cerr << "Error: Se excedió el límite de llamadas a perform_experiment" << endl;
        exit(1);
    }

    if ((int)E.size() != N) {
        cerr << "Error: Tamaño inválido del arreglo E" << endl;
        exit(1);
    }

    for (int i = 0; i < N; i++) {
        if (E[i] < -1 || E[i] > N) {
            cerr << "Error: Valor inválido en E[" << i << "] = " << E[i] << endl;
            exit(1);
        }
    }

    vector<int> S(N);
    for (int i = 0; i < N; i++) {
        S[i] = (E[i] == -1 ? C[i] : E[i]);
    }

    return count_components(S);
}

vector<int> find_colours(int N, vector<int> X, vector<int> Y){
    vector<int> v(N, -1);
    vector<int> r(N);
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            v.assign(N, j);
            v[i] = -1;
            if(perform_experiment(v) == 1){
                r[i] = j;
                break;
            } 
        }
    }
    return r;
}

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