Submission #1115100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115100		rqi	Sphinx's Riddle (IOI24_sphinx)	C++17	18 / 100	12 ms	504 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);

    DSU dsu; dsu.init(N);
    for(int i = 0; i+1 < N; i++){
        vi E = vi(N, N);
        E[i] = E[i+1] = -1;
        int query_res = my_experiment(E);
        assert(query_res == 1 || query_res == 2);
        if(query_res == 1){
            dsu.unite(i, i+1);
        }
    }

    for(int i = 0; i < N; i++){
        ans[i] = dsu.get(i);
    }

    return ans;
}

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