Submission #1244157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244157		alexander707070	Sphinx's Riddle (IOI24_sphinx)	C++20	100 / 100	680 ms	1652 KiB

sphinx

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

#include "sphinx.h"

using namespace std;

int n,m,root;
int color[MAXN];
int li[MAXN],tim,ans[MAXN];
vector<int> v[MAXN],g[MAXN],comp[MAXN];
vector<int> seq[2];

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]>=0 and color[x]>=0 and color[i]==color[x]) 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;
}

void find_components(){

    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();
            }
        }
    }

    for(int i=1;i<=n;i++){
        comp[graph.root(i)].push_back(i);
    }
}

void dfs2(int x,int side){
    li[x]=tim;
    seq[side].push_back(x);

    for(int i:g[x]){
        if(li[i]==tim)continue;
        dfs2(i,side^1);
    }
}

void fillc(int k,int c){
    for(int i:comp[k])color[i]=c;
}

void find_colors(int id){
    for(int curr=0;curr<n;curr++){

        for(int i:seq[id])fillc(i,-1);
        for(int i:seq[id^1])fillc(i,curr);

        vector<int> s=seq[id];

        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++)fillc(s[i],n);

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

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

            ans[s[l]]=curr;

            while(int(s.size())>l){
                fillc(s.back(),n);
                s.pop_back();
            }
        }
    }
}

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]);
    }

    find_components();

    for(int i=0;i<m;i++){
        int a=graph.root(X[i]);
        int b=graph.root(Y[i]);

        if(a==b)continue;
        g[a].push_back(b);
        g[b].push_back(a);

        root=a;
    }

    tim++;
    dfs2(root,0);

    vector<int> sol;

    if(seq[0].empty() or seq[1].empty()){

        for(int i=1;i<=n;i++)color[i]=-1;
        for(int curr=0;curr<n;curr++){
            color[1]=curr;
            if(query()==1){
                for(int f=1;f<=n;f++)sol.push_back(curr);
                return sol;
            }
        }
    }

    find_colors(0);
    find_colors(1);

    for(int i=1;i<=n;i++){
        sol.push_back(ans[graph.root(i)]);
    }

    return sol;
}

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