Submission #1178553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178553		alexander707070	Sphinx's Riddle (IOI24_sphinx)	C++20	3 / 100	39 ms	532 KiB

sphinx

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

using namespace std;

int n,m,in[MAXN],curr[MAXN];
vector<int> v[MAXN],subtree[MAXN];
bool connected[MAXN][MAXN],vis[MAXN];

int color[MAXN],res[MAXN];

struct unionfind{
    int dsu[MAXN];

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

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

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

    bool conn(int x,int y){
        return root(x)==root(y);
    }
}graph;

void dfs2(int x){
    vis[x]=true;

    for(int i:v[x]){
        if(!vis[i] and color[i]==color[x] and color[i]!=-1)dfs2(i);
    }
}

int calc_comps(){
    for(int i=1;i<=n;i++)vis[i]=false;
    int res=0;

    for(int i=1;i<=n;i++){
        if(!vis[i]){
            dfs2(i); res++;
        }
    }

    return res;
}

int experiment(){
    vector<int> e;
    for(int i=1;i<=n;i++)e.push_back(color[i]);

    return perform_experiment(e);
}

void findcolor(int x,vector<int> c){

    for(int i=1;i<=n;i++)color[i]=n;
    for(int i:c)color[i]=-1;
    color[x]=-1;

    while(!c.empty()){
        int l=-1,r=c.size(),tt;

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

            for(int f:c)color[f]=n;
            for(int f=c.size()-1;f>=tt;f--)color[c[f]]=-1;

            int comps=calc_comps();
            if(experiment()<comps){
                l=tt;
            }else{
                r=tt;
            }
        }

        if(l!=-1){
            graph.mergev(x,c[l]);

            while(int(c.size())>l){
                color[c.back()]=n;
                c.pop_back();
            }
        }else break;
    }
}

void dfs(int x,int p){
    in[x]=1;
    subtree[x]={x};
    vector<int> children;

    for(int i:v[x]){
        if(in[i]==0){
            dfs(i,x);
            
            children.push_back(i);
            for(int f:subtree[i])subtree[x].push_back(f);
        }
    }

    for(int i:children){        
        vector<int> c;
        for(int f:subtree[i]){
            if(!connected[f][x])continue;

            bool bad=false;
            for(int k:c){
                if(graph.conn(k,f))bad=true;
            }

            if(!bad)c.push_back(f);
        }

        findcolor(x,c);
    }

    in[x]=2;
}

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

    for(int i=1;i<=m;i++){
        v[X[i-1]+1].push_back(Y[i-1]+1);
        v[Y[i-1]+1].push_back(X[i-1]+1);

        connected[X[i-1]+1][Y[i-1]+1]=true;
        connected[Y[i-1]+1][X[i-1]+1]=true;
    }

    for(int i=0;i<2;i++){
        for(int c=0;c<n;c++){
            for(int f=1;f<=n;f++){
                if(f%2==i)curr[f]=c;
                else curr[f]=-1;
            }

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

            if(experiment()==n)continue;

            int len=n;

            while(len>1){
                int l=0,r=len,tt;
        
                while(l+1<r){
                    tt=(l+r)/2;

                    int ext=0;
                    if(tt>1)ext++;
                    if(len<n)ext++;

                    for(int f=1;f<=n;f++)color[f]=n;
                    for(int f=len;f>=tt;f--)color[f]=curr[f];

                    if(experiment()==ext+len-tt+1){
                        r=tt;
                    }else{
                        l=tt;
                    }
                }

                if(r==1)break;

                if((r-1)%2==i){
                    res[r]=c;
                    len=r-1;
                }else{
                    res[r-1]=c;
                    len=r-2;
                }
            }
        }
    }

    vector<int> ans;
    for(int i=1;i<=n;i++)ans.push_back(res[i]);

    return ans;
}

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