Submission #1115094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115094		rqi	Sphinx's Riddle (IOI24_sphinx)	C++17	10 / 100	425 ms	1716 KiB

sphinx

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

using vi = vector<int>;
using pi = pair<int, int>;
using vpi = vector<pi>;

#define sz(x) int((x).size())
#define pb push_back
#define mp make_pair
#define f first
#define s second

struct DSU{
    vi e;
    void init(int N){
        e = vi(N, -1);
    }
    int get(int x){
        if(e[x] == -1) return x;
        e[x] = get(e[x]);
        return e[x];
    }
    bool unite(int x, int y){
        x = get(x);
        y = get(y);
        if(x == y) return false;
        if(-e[x] < -e[y]) swap(x, y);
        e[y] = x;
        return true;
    }
};

const int mx = 255;
int N;
vpi eds;
vi adj[mx];

int my_experiment(vi E){
    DSU dsu;
    dsu.init(N);
    for(auto [a, b]: eds){
        if(E[a] == N && E[b] == N){
            dsu.unite(a, b);
        }
    }



    int neg_cnt = 0;
    for(int i = 0; i < N; i++){
        if(E[i] == N && dsu.get(i) == i){
            neg_cnt++;
        }
    }

    int query_res = perform_experiment(E);
    return query_res - neg_cnt;
}

vi find_colours(int _N, vi X, vi Y) {
    N = _N;
    int M = sz(X);
    for(int i = 0; i < M; i++){
        eds.pb(mp(X[i], Y[i]));
        adj[X[i]].pb(Y[i]);
        adj[Y[i]].pb(X[i]);
    }

    vi ans(N, -1);
    for(int i = 0; i < N; i++){
        int other_node = adj[i][0];
        for(int j = 0; j < N; j++){
            cerr << "nodes: " << i << " " << other_node << "\n";
            vi E(N, N);
            E[i] = -1;
            E[other_node] = j;
            int query_res = my_experiment(E);
            if(query_res == 1){
                ans[i] = j;
                break;
            }
        }
    }

    return ans;
}

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