Submission #1231292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231292		BigBadBully	Sphinx's Riddle (IOI24_sphinx)	C++20	100 / 100	730 ms	1888 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
//////////////////////////////////////////////////////////////////
vector<int> find_colours(int N, vector<int> X, vector<int> Y)
{
    auto n = N, m = (int)X.size();
    auto x = X, y = Y;
    vector<int> col(n, 0);
    for (int i = 0; i < n; i++)
        col[i] = i;
    vector<vector<int>> graph(n);
    for (int i = 0; i < m; i++)
        graph[x[i]].push_back(y[i]),
            graph[y[i]].push_back(x[i]);
    function<int(int)> fnd = [&](int x)
    {
        if (col[x] == x)
            return x;
        return col[x] = fnd(col[x]);
    };
    {

        auto povezan = [&](vector<int> tuff, int idx)
        {
            vector<int> salji(n, n);
            for (int i : tuff)
                salji[i] = -1;
            vector<bool> vis(n, 0);
            function<void(int)> dfs = [&](int cur)
            {
                if (vis[cur] || salji[cur] != n)
                    return;
                vis[cur] = 1;
                for (int a : graph[cur])
                    dfs(a);
            };
            salji[idx] = -1;
            set<int> dif;
            for (int i : tuff)
                dif.insert(fnd(col[i]));
            int comps = dif.size();
            for (int i = 0; i < n; i++)
                if (!vis[i] && salji[i] == n)
                {
                    comps++;
                    dfs(i);
                }
            return perform_experiment(salji) <= comps;
        };

        vector<int> pref;
        pref.push_back(0);
        for (int i = 1; i < n; i++)
        {
            if (povezan(pref, i))
            {
                set<int> used;
                vector<int> space;
                for (int a : graph[i])
                    if (a < i && used.count(fnd(a)) == 0)
                        space.push_back(a), used.insert(col[a]);
                sort(space.begin(), space.end());
                int k = space.size();
                auto fnd_next = [&](int cur)
                {
                    int bg = lower_bound(space.begin(), space.end(), cur) - space.begin();
                    int l = bg;
                    int r = k;
                    auto check = [&](int bnd)
                    {
                        if (bnd == k)
                            return true;
                        vector<int> src;
                        for (int j = bg; j <= bnd; j++)
                            src.push_back(space[j]);
                        return povezan(src, i);
                    };
                    if (!check(k-1))
                        return k;
                    while (r - l)
                    {
                        int mid = l + r >> 1;
                        if (check(mid))
                            r = mid;
                        else
                            l = mid + 1;
                    }
                    return l;
                };
                int cur = fnd_next(0);
                while (cur < k)
                {
                    col[fnd(space[cur])] = i;
                    cur = fnd_next(space[cur] + 1);
                }
            }
            pref.push_back(i);
        }
        for (int i = 0; i < n; i++)
            col[i] = fnd(i);
    }
    vector<int> ans(n,n-1);
    int isti = 0;
    {
        set<int> difs;
        for (int i = 0; i < n; i++)
            difs.insert(fnd(i));
        isti = difs.size();
    }
    vector<vector<int>> cols(n);
    for (int i = 0; i < n; i++)
        cols[fnd(i)].push_back(i);
    if (isti == 1){
        vector<int> salji(n,n);
        vector<int> ales;
        for (int c = 0; c < n; c++)
        {
            salji.assign(n,c);
            salji[0] = -1;
            ales.push_back(perform_experiment(salji));
        }
        ans[fnd(0)] = min_element(ales.begin(),ales.end())-ales.begin();
    }
    else
    {
        vector<vector<int>> g(n);
        for (int i = 0; i < m; i++)
        {
            if (fnd(x[i]) == fnd(y[i]))continue;
            g[fnd(x[i])].push_back(fnd(y[i]));
            g[fnd(y[i])].push_back(fnd(x[i]));
        }
        vector<int> bi(n,-1);
        function<void(int,int)> bic = [&](int cur,int prev)
        {
            bi[cur] = 1-bi[prev];
            for (int a : g[cur])
                if (bi[a]<0)
                    bic(a,cur);
        };
        bi[fnd(0)] = 1;
        bic(fnd(0),fnd(0));
        vector<int> a,b;
        for (int i = 0; i < n; i++)
            if (bi[fnd(i)])
                a.push_back(fnd(i));
            else
                b.push_back(fnd(i));
        sort(a.begin(),a.end());
        sort(b.begin(),b.end());
        a.resize(unique(a.begin(),a.end())-a.begin());
        b.resize(unique(b.begin(),b.end())-b.begin());
        for (int it = 0;it < 2; it++)
        {
            int p = a.size(),q = b.size();
            vector<bool> vis(n,0);
            vector<int> salji(n,0);
            function<void(int,int)> cntc = [&](int cur,int c)
            {
                if (vis[cur])return;
                vis[cur] = 1;
                for(auto a : graph[cur])
                    if (salji[a] == c)
                        cntc(a,c);
            };
            auto check = [&](vector<int> tuff, int c)
            {
                vis.assign(n,0);
                salji.assign(n,n);
                for (int i : b)
                    for (int x : cols[i])
                        salji[x] = c;
                for (int i : tuff)
                    for (int x : cols[i])
                        salji[x] = -1;
                int comps = 0;
                for (int i = 0; i < n; i++)
                {
                    if (!vis[i] && salji[i] == n)
                    {
                        comps++;
                        cntc(i,n);
                    }
                }
                for (int i = 0; i < n; i++)
                {
                    if (!vis[i] && salji[i] == c)
                    {
                        comps++;
                        cntc(i,c);
                    }
                }
                set<int> difs;
                for (int i = 0; i < n; i++)
                    if (salji[i] == -1)
                        difs.insert(fnd(i));
                comps+=difs.size();
                return perform_experiment(salji) < comps;
            };
            
            auto fnd_nxt = [&](int cur,int c)
            {       
                
                
                
                vector<int> koji;
                vector<int> v;
                for (int i = 0; i < p; i++)
                    if (ans[a[i]] == n-1)
                        v.push_back(a[i]),koji.push_back(i);
                int sz = v.size();
                int bg = lower_bound(v.begin(),v.end(),cur)-v.begin();
                auto salji = [&](int idx)
                {
                    vector<int> tuf;
                    if (idx == sz)return true;
                    for (int i = bg; i <= idx; i++)
                        tuf.push_back(v[i]);
                    return check(tuf,c);
                };
                if (!salji(sz-1)) return p;

                int l = bg,r = sz;
                while(r-l)
                {
                    int mid = l+r>>1;
                    if (salji(mid))
                        r = mid;
                    else
                        l = mid+1;
                } 
                if (r==sz)return p;
                return koji[l];
            };
            
            for (int c = 0; c < n-1; c++)
            {
                int cur = fnd_nxt(0,c);
                while(cur < p)
                {
                    ans[a[cur]] = c;
                    cur = fnd_nxt(a[cur]+1,c);
                }
            }
            swap(a,b);
        }
    }   

    for (int i = 0; i < n; i++)
        col[i] = ans[fnd(i)];
    return col;
}
///////////////////////////////////////////////////////////////////

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