Submission #1204429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204429		Zbyszek99	Sphinx's Riddle (IOI24_sphinx)	C++20	100 / 100	237 ms	1720 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

int n;
vi graph[251];
int my_root[251];
vi graph2[251];
int dist[251];
bool odw[251];
bool is_in[251];
vi my_verts[251];

int fint(int v) 
{
    if(my_root[v] == v) return v;
    my_root[v] = fint(my_root[v]);
    return my_root[v];
}

void onion(int a, int b)
{
    a = fint(a);
    b = fint(b);
    my_root[a] = b;
}

void dfs(int v, int d)
{
    odw[v] = 1;
    dist[v] = d;
    forall(it,graph2[v])
    {
        if(odw[it] == 0)
        {
            dfs(it,(d+1)%2);
        }
    }
}

vi ans;

void dfs_comp(int v)
{
    odw[v] = 1;
    forall(it,graph[v])
    {
        if(odw[it] == 0 && is_in[it]) dfs_comp(it);
    }
}

bool check_comps(vi& c0, int color)
{
    rep(i,n) odw[i] = 0;
    rep(i,n) is_in[i] = 1;
    vi query(n,color);
    forall(it,c0) forall(it2,my_verts[it]) query[it2] = -1;
    forall(it,c0) forall(it2,my_verts[it]) is_in[it2] = 0;
    set<int> dif;
    forall(it,c0) dif.insert(fint(it));
    int comps = siz(dif);
    rep(i,n)
    {
        if(odw[i] == 0 && is_in[i])
        {
            comps++;
            dfs_comp(i);
        }
    }
    return perform_experiment(query) != comps;
}

int sons_cnt(vi r, int v)
{
    rep(i,n) odw[i] = 0;
    rep(i,n) is_in[i] = 1;
    vi query(n,n);
    query[v] = -1;
    is_in[v] = 0;
    forall(it,r) query[it] = -1;
    forall(it,r) is_in[it] = 0;
    int comps = siz(r)+1;
    rep(i,n)
    {
        if(odw[i] == 0 && is_in[i] == 1)
        {
            comps++;
            dfs_comp(i);
        }
    }
    return comps-perform_experiment(query);
}

void solve(set<int> c0)
{
    rep(color,n)
    {
        while(true)
        {
            vi rest;
            forall(it,c0) rest.pb(it);
            if(!check_comps(rest,color)) break;
            int l = 0;
            int r = siz(rest)-1;
            while(l < r)
            {
                vi rest2;
                rep2(i,l,(l+r)/2) rest2.pb(rest[i]);
                if(check_comps(rest2,color)) r = (l+r)/2;
                else l = (l+r)/2+1;
            }
            int root = fint(rest[l]);
            rep(i,n)
            {
                if(fint(i) == root)
                {
                    ans[i] = color;
                }
            }
            c0.erase(c0.find(root));
        }
    }
}

vi find_colours(int N, vi X, vi Y) 
{
    n = N;
    ans.resize(n,-1);
    rep(i,n) my_root[i] = i;
    rep(i,siz(X))
    {
        graph[X[i]].pb(Y[i]);
        graph[Y[i]].pb(X[i]);
    }
    rep(i,n)
    {
        int cnt = 1;
        set<int> comps;
        vi ro2;
        forall(it,graph[i]) 
        {
            if(it < i && comps.find(fint(it)) == comps.end()) 
            {
                comps.insert(fint(it));
                ro2.pb(it);
                cnt++;
            }
        }
        int sons = sons_cnt(ro2,i);
        if(sons == 0) continue;
        else
        {
            rep(j,sons)
            {
                vi ro;
                forall(it,ro2)
                {
                    if(fint(it) != fint(i))
                    {
                        ro.pb(it);
                    }
                }
                int l = 0;
                int r = siz(ro)-1;
                while(l < r)
                {
                    vi r2;
                    rep2(i,l,(l+r)/2) r2.pb(ro[i]);
                    if(sons_cnt(r2,i) != 0) r = (l+r)/2;
                    else l = (l+r)/2+1;
                }
                onion(i,ro[l]);
            }
        }
    }
    rep(i,n)
    {
        forall(it,graph[i])
        {
            graph2[fint(i)].pb(fint(it));
        }
    }
    int roots_cnt = 0;
    rep(i,n) odw[i] = 0;
    rep(i,n)
    {
        if(fint(i) == i)
        {
            dfs(i,0);
            break;
        }
    }
    rep(i,n)
    {
        my_verts[fint(i)].pb(i);
        if(fint(i) == i)
        {
            roots_cnt++;
        }
    }
    if(roots_cnt == 1)
    {
        rep(i,n)
        {
            vi query(n,-1);
            query[0] = i;
            if(perform_experiment(query) == 1)
            {
                rep(j,n)
                {
                    ans[j] = i;
                }
                break;
            }
        }
        return ans;
    }
    set<int> s[2];
    rep(i,n)
    {
        if(fint(i) == i)
        {
            s[dist[i]].insert(i);
        }
    }
    solve(s[0]);
    solve(s[1]);
    return ans;
}

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