Submission #1244110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244110		alexander707070	Sphinx's Riddle (IOI24_sphinx)	C++20	50 / 100	153 ms	1176 KiB

sphinx

#include<bits/stdc++.h>
#define MAXN 307

#include "sphinx.h"

using namespace std;

int n,m;
int color[MAXN];
int li[MAXN],tim;
vector<int> v[MAXN];

int query(){
    vector<int> w;
    for(int i=1;i<=n;i++){
        w.push_back(color[i]);
    }

    return perform_experiment(w);
}

struct union_find{
    int dsu[MAXN];

    void init(){
        for(int i=1;i<=n;i++)dsu[i]=i;
    }

    int root(int x){
        if(dsu[x]==x)return x;
        dsu[x]=root(dsu[x]);
        return dsu[x];
    }

    void mergev(int x,int y){
        int rootx=root(x);
        int rooty=root(y);
        dsu[rootx]=rooty;
    }
}graph;

void dfs(int x){
    li[x]=tim;

    for(int i:v[x]){
        if(li[i]==tim)continue;
        if((color[i]==n and color[x]==n) or (graph.root(i)==graph.root(x) and color[i]==-1 and color[x]==-1)){
            dfs(i);
        }
    }
}

int calc_comps(){
    tim++;

    int c=0;
    for(int i=1;i<=n;i++){
        if(li[i]==tim)continue;
        c++;

        dfs(i);
    }

    return c;
}

vector<int> find_colours(int N, vector<int> X, vector<int> Y){
    n=N; m=int(X.size());

    for(int i=0;i<m;i++){
        X[i]++; Y[i]++;

        v[X[i]].push_back(Y[i]);
        v[Y[i]].push_back(X[i]);
    }

    for(int i=1;i<=n;i++)color[i]=n;
    graph.init();

    for(int i=1;i<=n;i++){

        for(int f=1;f<=n;f++)color[f]=n;
        color[i]=-1;

        tim++;
        vector<int> s;

        for(int f:v[i]){
            if(f>i)continue;

            if(li[graph.root(f)]!=tim){
                color[f]=-1;
                s.push_back(f);
            }

            li[graph.root(f)]=tim;
        }

        while(!s.empty()){
            if(calc_comps()==query())break;

            int l=0,r=s.size(),tt;

            while(l+1<r){
                tt=(l+r)/2;

                for(int i=0;i<tt;i++)color[s[i]]=n;

                if(calc_comps()==query()){
                    r=tt;
                }else{
                    l=tt;
                }

                for(int i=0;i<tt;i++)color[s[i]]=-1;
            }

            graph.mergev(i,s[l]);
            while(int(s.size())>l){
                color[s.back()]=n;
                s.pop_back();
            }
        }
    }

    vector<int> sol;
    for(int i=1;i<=n;i++){
        sol.push_back(graph.root(i)-1);
    }

    return sol;
}

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