Submission #1105458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105458		jerzyk	Sphinx's Riddle (IOI24_sphinx)	C++17	100 / 100	642 ms	1728 KiB

sphinx

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

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 250 + 7;
int fau[N], ansclr[N];
vector<int> ed[N], ed2[N];
bool vis[N];
vector<int> dfst, vset[2];

int Find(int v)
{
    if(fau[v] == v) return v;
    return (fau[v] = Find(fau[v]));
}

void Union(int a, int b)
{
    //cout << "Union " << a << " " << b << "\n";
    a = Find(a); b = Find(b);
    fau[max(a, b)] = min(a, b);
}

void DFSN2(int v)
{
    vis[v] = true;
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(Find(v) != Find(ed[v][i]))
            ed2[Find(v)].pb(Find(ed[v][i]));
        if(vis[ed[v][i]])
            continue;
        DFSN2(ed[v][i]);
    }
}

void DFSclr(int v, int c)
{
    vis[v] = true;
    vset[c].pb(v);
    for(int i = 0; i < (int)ed2[v].size(); ++i)
        if(!vis[ed2[v][i]])
            DFSclr(ed2[v][i], c ^ 1);
}

void DoNew(int n)
{
    DFSN2(0);
    for(int i = 0; i < n; ++i) vis[i] = false;
    for(int i = 0; i < n; ++i)
    {
        vector<int> nw;
        sort(ed2[i].begin(), ed2[i].end());
        for(int j = 0; j < (int)ed2[i].size(); ++j)
            if(j == 0 || ed2[i][j] != ed2[i][j - 1])
                nw.pb(ed2[i][j]);
        ed2[i] = nw;
    }
    DFSclr(0, 0);
    for(int i = 0; i < n; ++i) vis[i] = false;
}

void DFS(int v)
{
    vis[v] = true;
    for(int i = 0; i < (int)ed[v].size(); ++i)
        if((!vis[ed[v][i]]) && dfst[ed[v][i]] == dfst[v])
            DFS(ed[v][i]);
}

int Sus(vector<int> que)
{
    int ans = 0, n = que.size();
    dfst.clear();
    for(int i = 0; i < n; ++i)
        if(que[i] != -1)
            dfst.pb(que[i]);
        else
            dfst.pb(-Find(i) - 1);
    for(int i = 0; i < n; ++i)
        if(!vis[i])
        {
            ++ans;
            DFS(i);
        }
    for(int i = 0; i < n; ++i) vis[i] = false;
    return ans;
}

void D1(int n)
{
    vector<int> bas(n, -1), que;
    for(int i = 0; i < n; ++i)
    {
        que = bas;
        que[1] = i;
        if(perform_experiment(que) == 1)
            ansclr[0] = i;
    }
}

void FindClr(int n)
{
    vector<int> bas(n, -1), cur, que;
    cur = vset[1];
    //cerr << "beg " << vset[1].size() << "\n";
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < (int)vset[0].size(); ++j)
            bas[vset[0][j]] = i;
        for(int j = 0; j < (int)vset[1].size(); ++j)
            bas[vset[1][j]] = -1;
        for(int j = 0; j < n; ++j) bas[j] = bas[Find(j)];
        que = bas;
        //for(int j = 0; j < n; ++j)
            //cout << que[j] << " ";
        //cout << "\n";
        int ant = Sus(que);
        int akt = perform_experiment(que);
        int il = ant - akt;
        //cerr << "Clr: " << i << " " << ant << " " << akt << "\n";
        while(il > 0)
        {
            int p = 0, s, k = (int)cur.size() - 1;
            while(p < k)
            {
                s = (p + k) / 2;
                que = bas;
                for(int j = s + 1; j < (int)cur.size(); ++j)
                    que[cur[j]] = n;
                for(int j = 0; j < n; ++j) que[j] = que[Find(j)];
                int abc = Sus(que);
                if(perform_experiment(que) < abc)
                    k = s;
                else
                    p = s + 1;
            }
            //if(cur.size() == 0) return;
            //cerr << "F: " << cur[p] << " " << il << "\n";
            que = bas;
            //for(int j = 0; j < n; ++j)
                //cerr << que[j] << " ";
            //cout << "\n";
            int xd = Sus(que);
            que[cur[p]] = i;
            for(int j = 0; j < n; ++j) que[j] = que[Find(j)];
            /*for(int j = 0; j < n; ++j)
                cerr << que[j] << " ";
            cerr << "\n";*/
            int xd2 = Sus(que);
            //cerr << xd << " " << xd2 << "\n";
            il -= (xd - xd2);
            ansclr[cur[p]] = i;
            bas[cur[p]] = i;
            for(int j = 0; j < n; ++j) bas[j] = bas[Find(j)];
            vector<int> nw;
            for(int j = 0; j < (int)cur.size(); ++j)
                if(j != p)
                nw.pb(cur[j]);
            cur = nw;
        }
    }
}

void FN(int v, int il, int n)
{
    vector<int> cur, bas(n, n), que, ss;
    
    for(int i = 0; i < (int)ed[v].size(); ++i)
        if(!vis[Find(ed[v][i])] && ed[v][i] < v)
        {
            cur.pb(Find(ed[v][i]));
            vis[cur.back()] = true;
        }
    for(int i = 0; i < (int)cur.size(); ++i)
        vis[cur[i]] = false;
    while(il--)
    {
        int p = 0, s, k = cur.size() - 1;
        while(p < k)
        {
            s = (p + k) / 2;
            que = bas;
            for(int i = 0; i <= s; ++i)
                que[cur[i]] = -1;
            que[v] = -1;
            for(int i = 0; i < n; ++i) que[i] = que[Find(i)];
            int ans = perform_experiment(que);
            int ant = Sus(que);
            if(ans < ant)
                k = s;
            else
                p = s + 1;
        }
        ss.pb(cur[p]);
        vector<int> nw;
        for(int i = p + 1; i < (int)cur.size(); ++i) nw.pb(cur[i]);
        cur = nw;
    }
    for(int i = 0; i < (int)ss.size(); ++i)
        Union(v, ss[i]);
}

vector<int> find_colours(int _N, vector<int> _X, vector<int> _Y)
{
    int n = _N;
    vector<int> answer;
    for(int i = 0; i < (int)_X.size(); ++i)
    {
        ed[_X[i]].pb(_Y[i]);
        ed[_Y[i]].pb(_X[i]);
    }
    vector<int> cq(n, n);
    for(int i = 0; i < n; ++i)
        fau[i] = i;

    cq[0] = -1;
    for(int i = 1; i < n; ++i)
    {
        cq[i] = -1;
        int akt = perform_experiment(cq);
        int ant = Sus(cq);
        //cerr << "F:\n";
        //for(int j = 0; j < n; ++j)
            //cerr << Find(j) << " ";
        //cout << "\n";
        //cerr << "Sp: " << i << " " << akt << " " << ant << "\n";
        FN(i, ant - akt, n);
    }
    DoNew(n);
    if((int)vset[1].size() == 0)
        D1(n);
    else
    {
        FindClr(n);
        swap(vset[1], vset[0]);
        FindClr(n);
    }

    for(int i = 0; i < n; ++i)
        answer.pb(ansclr[Find(i)]);
    return answer;
}

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