Submission #1178537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178537		alexander707070	스핑크스 (IOI24_sphinx)	C++20	50 / 100	294 ms	1544 KiB

sphinx

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

using namespace std;

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

int color[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;
    }

    graph.init();
    dfs(1,0);

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

    return ans;
}

• 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