Submission #1199051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199051		modwwe	Sphinx's Riddle (IOI24_sphinx)	C++20	100 / 100	389 ms	2112 KiB

sphinx

#include "sphinx.h"
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int   long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1apio"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
using i128 = __int128;
int rand(int l,int r)
{
    return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const ll inf=1e15;
const ll mod2 =998244353;
//const ll base=67;
ll  n, m, s1, s2, s4, s3, sf, k, s5, s6, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
ll  i, s10, s12,k1,k2,k3,s11,lim,w,l,r,dem5,dem6,dem7,dem9,now,root,q,en;
ll kk;
ll el = 19;
struct ib
{
    int a,b;
};
struct dsuconcu
{
    ib dsu[5001];
    void reset()
    {
        for(int i=1; i<=n; i++)
            dsu[i]= {1,i};
    }
    int get(int x)
    {
        if(x!=dsu[x].b)dsu[x].b=get(dsu[x].b);
        return dsu[x].b;
    }
    bool noi(int x,int y)
    {
        x=get(x);
        y=get(y);
        if(x==y)return 0;
        if(dsu[x].a<dsu[y].a)swap(x,y);
        dsu[x].a+=dsu[y].a;
        dsu[y].b=x;
        return 1;
    }
} ds,ds2;
int ok[5001];
vector<ib> edge;
vector<int> v[5001],ke[5001],dc[5001];
int depth[5001];
int c[5001];
int d[5001];
void dfs(int x)
{
    ok[x]=1;
    for(auto f:v[x])
    {
        if(!ok[f])dfs(f),ke[x].pb(f);
        else if(ok[f]==1) dc[x].pb(f);
    }
    ok[x]=2;
}
bool ask(vector<int>d,int x)
{
    dem++;
    for(int i=1; i<=n; i++)
        c[i]=dem;
    for(int i=0; i<d.size(); i++)
        c[ds.get(d[i])]=dem-1;
    ds2.reset();
    for(int i=1; i<=n; i++)
        c[i]=c[ds.get(i)];
    dem2=n;
    for(auto x:edge)
    {
        if(c[x.a]==c[x.b]&&c[x.a]==dem)
        {
            if(ds2.noi(x.a,x.b))
                dem2--;
        }
        else if(ds.get(x.a)==ds.get(x.b))
        {
            if(ds2.noi(x.a,x.b))
                dem2--;
        }
    }
    vector<int> gc;
    for(int i=1; i<=n; i++)
        if(c[i]==dem)gc.pb(x);
        else gc.pb(-1);
    s10=perform_experiment(gc);
    s9=dem2-s10;
    return s9>0;
}
void dnc(vector<int>v,int x,int a)
{
    if(v.size()==a)
    {
        for(int i=0; i<v.size(); i++)
            ds.noi(v[i],x);
        return;
    }
    vector<int> lft,rgt;
    int mid=v.size()>>1;
    for(int i=0; i<mid; i++)
        lft.pb(v[i]);
    for(int i=mid; i<v.size(); i++)
        rgt.pb(v[i]);
    lft.pb(x);
    bool hihi=ask(lft,n);
    lft.pop_back();
    int ss=s9;
    if(ss!=a)dnc(rgt,x,a-s9);
    if(ss!=0)
        dnc(lft,x,ss);
}
void work(int x)
{
    vector<int> vc;
    for(auto f:dc[x])
        vc.pb(ds.get(f));
    sort(vc.begin(),vc.end());
    vc.erase(unique(vc.begin(),vc.end()),vc.end());
    vc.pb(x);
    if(ask(vc,n))
    {
        vc.pop_back();
        dnc(vc,x,s9);
    }
}
void des(int x)
{
    if(dc[x].size()!=0)work(x);
    for(auto f:ke[x])
        des(f);
}
void dfc(int x)
{
    ok[x]=1;
    for(auto f:v[x])
    {
        if(!ok[f])
        {
            depth[f]=depth[x]+1;
            dfc(f);

        }
    }
}
bool askk(vector<int>d,int x,vector<int>haha)
{
    dem++;
    for(int i=1; i<=n; i++)
        c[i]=dem;
    for(int i=0;i<haha.size();i++)
    c[ds.get(haha[i])]=dem-1;
    for(int i=0; i<d.size(); i++)
        c[ds.get(d[i])]=dem-1;
    ds2.reset();
    for(int i=1; i<=n; i++)
        c[i]=c[ds.get(i)];
    dem2=n;
    for(auto x:edge)
    {
        if(c[x.a]==c[x.b]&&c[x.a]==dem)
        {
            if(ds2.noi(x.a,x.b))
                dem2--;
        }
        else if(ds.get(x.a)==ds.get(x.b))
        {
            if(ds2.noi(x.a,x.b))
                dem2--;
        }
    }
    vector<int> gc;
    for(int i=1; i<=n; i++)
        if(c[i]==dem)gc.pb(x);
        else gc.pb(-1);
    s10=perform_experiment(gc);
    s9=dem2-s10;
    return s9>0;
}
void dnb(vector<int> v,int x,int lst,vector<int> lfec)
{
    assert(v.size()!=0);
    if(v.size()==1)
    {
        for(int i=0; i<v.size(); i++)
            d[v[i]]=x;
        return;
    }
    vector<int> lft,rgt;
    int mid=v.size()>>1;
    for(int i=0; i<mid; i++)
        lft.pb(v[i]);
    for(int i=mid; i<v.size(); i++)
        rgt.pb(v[i]);
    askk(lft,x,lfec);
    int ss=s9;
    if(ss==0)
    {
        for(auto g:lft)
        lfec.pb(g);
    }
    if(ss!=lst)
    {
        if(ss==0)
        {
            dnb(rgt,x,lst,lfec);
        }else{
        askk(rgt,x,lfec);
        dnb(rgt,x,s9,lfec);
        }
    }
    if(ss!=0)dnb(lft,x,ss,lfec);
}
void go(int x)
{
    vector<int>kaka;
    for(int i=0; i<2; i++)
    {
        for(int j=1; j<=n; j++)
            if(ds.get(j)==j&&d[j]==-1&&depth[j]%2==i)
                kaka.pb(j);
        if(kaka.size()!=0)
        {
            if(ask(kaka,x))
            {
                dnb(kaka,x,s9,{});
            }
        }
        kaka.clear();
    }
}
vector<int>  find_colours(int N,vector<int> X,vector<int> Y)
{
    n=N;
    m=X.size();
    ds.reset();
    for(int i=0; i<m; i++)
        v[X[i]+1].pb(Y[i]+1),
        v[Y[i]+1].pb(X[i]+1),
        edge.pb({X[i]+1,Y[i]+1});
    dfs(1);
    des(1);
    vector<int> ans;
    for(int i=1; i<=n; i++)
        v[i].clear(),ok[i]=0,d[i]=-1;
    ds2.reset();
    bool hihi=0;
    for(auto x:edge)
        if(ds2.get(ds.get(x.a))!=ds2.get(ds.get(x.b)))
        {
            hihi=1;
            ds2.noi(ds.get(x.a),ds.get(x.b));
            v[ds.get(x.a)].pb(ds.get(x.b));
            v[ds.get(x.b)].pb(ds.get(x.a));
        }
    if(!hihi)
    {
        vector<int> g;
        for(int i=0; i<n; i++)
            g.pb(-1);
        for(int i=0; i<n; i++)
        {
            g[0]=i;
            if(perform_experiment(g)==1)
            {
                ans.clear();
                for(int j=0; j<n; j++)
                    ans.pb(i);
                return ans;
            }
        }
        assert(0);
    }
    dfc(ds.get(1));
    for(int i=0; i<n; i++)
    {
        go(i);
    }
    for(int i=0; i<n; i++)
    {
        ans.pb(d[ds.get(i+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